The planar slope number of planar partial 3-trees of bounded degree

DOI10.1007/S00373-012-1157-ZMaRDI QIDQ354442zbMATH OpenOpenAlexFDO

Authors Vít Jelínek, Eva Jelínková, Jan Kratochvíl, Bernard Lidický, Marek Tesař, Tomáš Vyskočil

Publication date 19 July 2013

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.4137

zbMATH Keywords

planar graphsgraph drawingplanar slope numberslopes

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: It is known that every planar graph has a planar embedding where edges are represented by non-crossing straight-line segments. We study the planar slope number, i.e., the minimum number of distinct edge-slopes in such a drawing of a planar graph with maximum degree $Delta$. We show that the planar slope number of every planar partial 3-tree and also every plane partial 3-tree is at most $O(Delt{a}^5)$. In particular, we answer the question of Dujmovi'c et al. [Computational Geometry 38 (3), pp. 194--212 (2007)] whether there is a function $f$ such that plane maximal outerplanar graphs can be drawn using at most $f(Delta)$ slopes.

Recommendations

• The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree
• Planar and plane slope number of partial 2-trees
• Drawings of planar graphs with few slopes and segments

Cites work

• scientific article; zbMATH DE number 3047038 (Why is no real title available?)
• Bounded-degree graphs can have arbitrarily large slope numbers
• Bounded-degree graphs have arbitrarily large geometric thickness
• Drawability of Complete Graphs Using a Minimal Slope Set
• Drawing Cubic Graphs with at Most Five Slopes
• Drawing Cubic Graphs with the Four Basic Slopes
• Drawings of planar graphs with few slopes and segments
• Geometric representation of cubic graphs with four directions
• Graph Drawing
• Graph drawings with few slopes
• The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree

Cited in

(21)

• Universal slope sets for 1-bend planar drawings
• Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles
• Planar drawings with few slopes of Halin graphs and nested pseudotrees
• Drawings of planar graphs with few slopes and segments
• Planar drawings with few slopes of Halin graphs and nested pseudotrees
• Drawing subcubic planar graphs with four slopes and optimal angular resolution
• Planar and plane slope number of partial 2-trees
• The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree
• Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles
• Outerplanar graph drawings with few slopes
• Upward planar drawings with three and more slopes
• 1-bend upward planar slope number of SP-digraphs
• The Planar Slope Number of Subcubic Graphs
• Upward planar drawings with two slopes
• On the 3-tree core of plane graphs
• Upward Planar Drawings with Three and More Slopes
• Trees and Co-trees with Bounded Degrees in Planar 3-connected Graphs
• Universal slope sets for upward planar drawings
• 1-bend upward planar drawings of SP-digraphs
• On the complexity of the planar slope number problem
• Drawing partial 2-trees with few slopes

This page was built for publication: The planar slope number of planar partial 3-trees of bounded degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q354442)