HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

# On Point-sets that Support Planar Graphs

3 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry, Inria Nancy - Grand Est
Abstract : A universal point-set supports a crossing-free drawing of any planar graph. For a planar graph with $n$ vertices, if bends on edges of the drawing are permitted, universal point-sets of size $n$ are known, but only if the bend points are in arbitrary positions. If the locations of the bend points must also be specified as part of the point set, we prove that any planar graph with $n$ vertices can be drawn on a universal set $\cal S$ of $O(n^2/\log n)$ points with at most one bend per edge and with the vertices and the bend points in $\cal S$. If two bends per edge are allowed, we show that $O(n\log n)$ points are sufficient, and if three bends per edge are allowed, $O(n)$ points are sufficient. When no bends on edges are permitted, no universal point-set of size $o(n^2)$ is known for the class of planar graphs. We show that a set of $n$ points in balanced biconvex position supports the class of maximum-degree-3 series-parallel lattices.
Document type :
Journal articles
Complete list of metadata

Cited literature [13 references]

https://hal.inria.fr/hal-00684510
Contributor : Sylvain Lazard Connect in order to contact the contributor
Submitted on : Monday, April 2, 2012 - 12:17:43 PM
Last modification on : Thursday, January 20, 2022 - 4:16:33 PM

### Files

journalversion.pdf
Files produced by the author(s)

### Citation

Vida Dujmović, Will Evans, Sylvain Lazard, William Lenhart, Giuseppe Liotta, et al.. On Point-sets that Support Planar Graphs. Computational Geometry, Elsevier, 2013, 43 (1), pp.29--50. ⟨10.1016/j.comgeo.2012.03.003⟩. ⟨hal-00684510⟩

Record views