# Drawing Planar Graphs of Bounded Degree with Few Slopes

@inproceedings{Keszegh2010DrawingPG, title={Drawing Planar Graphs of Bounded Degree with Few Slopes}, author={Bal{\'a}zs Keszegh and J{\'a}nos Pach and D{\"o}m{\"o}t{\"o}r P{\'a}lv{\"o}lgyi}, booktitle={Graph Drawing}, year={2010} }

We settle a problem of Dujmovic, Eppstein, Suderman, and Wood by showing that there exists a function f with the property that every planar graph G with maximum degree d admits a drawing with noncrossing straight-line edges, using at most f(d) different slopes. If we allow the edges to be represented by polygonal paths with one bend, then 2d slopes suffice. Allowing two bends per edge, every planar graph with maximum degree d ≥ 3 can be drawn using segments of at most ⌈d/2⌉ different slopes… Expand

#### 27 Citations

The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree

- Mathematics, Computer Science
- Graphs Comb.
- 2013

It is shown that the planar slope number of every planar partial 3-tree and also every plane partial 2-tree is at most O(Δ5), and the question of Dujmović et al. (Comput Geom 38(3):194–212, 2007) whether there is a function f such that plane maximal outerplanar graphs can be drawn using at most f( Δ) slopes is answered. Expand

Planar Drawings with Few Slopes of Halin Graphs and Nested Pseudotrees

- Computer Science
- WADS
- 2021

This paper proves psn(G) ∈ Θ(∆) when G is a Halin graph, and thus has treewidth three, and presents the first polynomial upper bound on the planar slope number for a family of graphs havingtreewidth four, and shows that O(∅) slopes suffice for nested pseudotrees. Expand

Upward Planar Drawings with Three and More Slopes

- Computer Science
- 2021

It is shown that in general NP-hard to decide whether a given directed graph with maximum in and outdegree at most k admits such a drawing with k slopes, and for cactus graphs deciding and constructing a drawing can be done in polynomial time. Expand

Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles

- Mathematics, Computer Science
- Graph Drawing
- 2018

Lower bounds for the slope number of straight-line 1-planar drawings in terms of number of vertices and maximum degree are proved. Expand

Drawing Outer 1-planar Graphs with Few Slopes

- Mathematics, Computer Science
- Graph Drawing
- 2014

It is shown that an outer 1-planar graph G of bounded degree Δ admits an outer 3-line drawing that uses OΔ different slopes, which extends a previous result by Knauer et al. about the planar slope number of outerplanar graphs CGTA. Expand

Outerplanar Graph Drawings with Few Slopes

- Mathematics, Computer Science
- COCOON
- 2012

It is proved that Δ − 1 directions suffice for every outerplanar graph with maximum degree Δ ≥ 4, which improves the previous bound of O(Δ5), which was shown for planar partial 3-trees, a superclass of outerPlanar graphs. Expand

Planar Octilinear Drawings with One Bend Per Edge

- Mathematics, Computer Science
- Graph Drawing
- 2014

This paper proves that every 4-planar graph admits a planar octilinear drawing with at most one bend per edge on an integer grid of size On 2 ×On, and gives a class of graphs whose planarOctILinear drawings require at least two bends per edge. Expand

On the Total Number of Bends for Planar Octilinear Drawings

- Mathematics, Computer Science
- J. Graph Algorithms Appl.
- 2017

The first (non-trivial) upper bound on the required number of bends is derived from a result on the planar slope number of graphs by Keszegh et al. Expand

The Complexity of Bendless Three-Dimensional

- Mathematics
- 2013

We consider embeddings of 3-regular graphs into 3-dimensional Cartesian coordinates, in such a way that two vertices are adjacent if and only if two of their three coordinates are equal (that is, if… Expand

Contact Representations of Sparse Planar Graphs

- Computer Science, Mathematics
- ArXiv
- 2015

It is shown that every plane ( 2, 2)-sparse graph has a CCA-representation, and that any plane (2, 1)-tight graph or (2 - 0)-tightgraph dual to a (2- 3)-tightGraph or (1, 4-tight graph) has aCCA- Representation; and that finding such a representation for a plane(2, 0)- Tight graph with maximum degree 5 is an NP-complete problem. Expand

#### References

SHOWING 1-10 OF 48 REFERENCES

The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree

- Computer Science, Mathematics
- Graph Drawing
- 2009

The planar slope number, i.e., the minimum number of distinct edge-slopes in such a drawing of a planar graph with maximum degree Δ, is studied to answer the question whether there is a function f such that plane maximal outerplanar graphs can be drawn using at most f(Δ) slopes. Expand

Drawings of planar graphs with few slopes and segments

- Computer Science, Mathematics
- Comput. Geom.
- 2007

It is proved that every 3-connected plane graph on n vertices has a plane drawing with at most 5 n segments and at most 2n slopes. Expand

How to draw a planar graph on a grid

- Mathematics, Computer Science
- Comb.
- 1990

It is shown that any setF, which can support a Fáry embedding of every planar graph of sizen, has cardinality at leastn+(1−o(1))√n which settles a problem of Mohar. Expand

Graph drawings with few slopes

- Computer Science, Mathematics
- Comput. Geom.
- 2007

It follows that the slope-number of interval graphs, cocomparability graphs, and AT-free graphs is at most a function of the maximum degree, and it is proved that graphs of bounded degree and bounded treewidth have slope- number at most. Expand

Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness

- Mathematics, Computer Science
- Electron. J. Comb.
- 2006

This work proves that there exists Delta-regular graphs with arbitrarily large geometric thickness, and proves that for all Delta >= 9 and for all large n, there exists a Delta- regular graph with geometric thickness at least c Delta^{1/2} n^{1 /2 - 4/Delta - epsilon}. Expand

Crossing Number of Toroidal Graphs

- Mathematics, Computer Science
- Graph Drawing
- 2005

It is shown that if a graph of n vertices can be drawn on the torus without edge crossings and the maximum degree of its vertices is at most d, then its planar crossing number cannot exceed cdn,… Expand

Planar Drawings and Angular Resolution: Algorithms and Bounds (Extended Abstract)

- Mathematics, Computer Science
- ESA
- 1994

The first nontrivial upper bound on the angular resolution of planar straight-line drawings is proved, and a continuous trade-off between the area and theangular resolution is shown. Expand

On the angular resolution of planar graphs

- Mathematics, Computer Science
- STOC '92
- 1992

A very natural linear program is analyzed that bounds the angular resolution of any fixed planar graph G from &OHgr;(1/<italic>d</italic>, although currently, it is unable to settle whether or not this lower bound is existentially tight (up to constant α). Expand

The geometric thickness of low degree graphs

- Computer Science, Mathematics
- SCG '04
- 2004

It is proved that the geometric thickness of graphs whose maximum degree is no more than four is two, and an embedding algorithm for graphs with maximum degree three that uses an n x n grid and a more complex algorithm for embedding a graph withmaximum degree four. Expand

General theoretical results on rectilinear embedability of graphs

- Mathematics
- 1991

In the design of certain kinds of electronic circuits the following question arises: given a non-negative integerk, what graphs admit of a plane embedding such that every edge is a broken line formed… Expand