Mixed Linear Layouts of Planar Graphs

Pupyrev, Sergey (2017) Mixed Linear Layouts of Planar Graphs. In: Graph Drawing and Network Visualization, GD 2017, September 25-27 , pp. 197-209(Official URL: https://doi.org/10.1007/978-3-319-73915-1_17).

Full text not available from this repository.


A k-stack (respectively, k-queue) layout of a graph consists of a total order of the vertices, and a partition of the edges into k sets of non-crossing (non-nested) edges with respect to the vertex ordering. In 1992, Heath and Rosenberg conjectured that every planar graph admits a mixed 1-stack 1-queue layout in which every edge is assigned to a stack or to a queue that use a common vertex ordering. We disprove this conjecture by providing a planar graph that does not have such a mixed layout. In addition, we study mixed layouts of graph subdivisions, and show that every planar graph has a mixed subdivision with one division vertex per edge.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.490 Embeddings
P Styles > P.999 Others
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1604

Actions (login required)

View Item View Item