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

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
2018
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11391/1420984`
• ND
• 16
• 8