A drawing of a graph such that the vertices are drawn as points along a line and each edge is a circular arc in one of the two half-planes defined by this line is called a -page drawing. If all edges are in the same half-plane, the drawing is called a -page drawing. We want to compute -page and -page drawings of planar graphs such that the number of crossings per edge does not depend on the number of vertices. We show that for any constant , there exist planar graphs that require more than crossings per edge in both -page and -page drawings. We then prove that if the vertex degree is bounded by , every planar 3-tree has a -page drawing with a number of crossings per edge that only depends on . Finally, we show a similar result for -page drawings of partial -trees.
1-page and 2-page drawings with bounded number of crossings per edge
Binucci, Carla;DI GIACOMO, Emilio;Liotta, Giuseppe
2018
Abstract
A drawing of a graph such that the vertices are drawn as points along a line and each edge is a circular arc in one of the two half-planes defined by this line is called a -page drawing. If all edges are in the same half-plane, the drawing is called a -page drawing. We want to compute -page and -page drawings of planar graphs such that the number of crossings per edge does not depend on the number of vertices. We show that for any constant , there exist planar graphs that require more than crossings per edge in both -page and -page drawings. We then prove that if the vertex degree is bounded by , every planar 3-tree has a -page drawing with a number of crossings per edge that only depends on . Finally, we show a similar result for -page drawings of partial -trees.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
