Mixed linear layouts of planar graphs

DOI10.1007/978-3-319-73915-1_17MaRDI QIDQ4625112zbMATH OpenOpenAlexFDO

Authors Sergey Pupyrev

Publication date 20 February 2019

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.00285

zbMATH Keywords

\(k\)-queue layoutmixed 1-stack 1-queue layout

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: 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.

Recommendations

• Stacks, queues and tracks: layouts of graph subdivisions
• Graph Drawing
• Laying Out Graphs Using Queues
• scientific article; zbMATH DE number 2159644
• An improved upper bound on the queue number of planar graphs

Cites work

• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Embedding planar graphs in four pages
• Graph layouts via layered separators
• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• scientific article; zbMATH DE number 1011685 (Why is no real title available?)
• scientific article; zbMATH DE number 2159644 (Why is no real title available?)
• Laying Out Graphs Using Queues
• On the Queue Number of Planar Graphs
• On the queue-number of graphs with bounded tree-width
• Radial Level Planarity Testing and Embedding in Linear Time
• Stack and queue number of 2-trees
• Stacks, queues and tracks: layouts of graph subdivisions
• The book embedding problem from a SAT-solving perspective
• The book thickness of a graph

Cited in

(21)

• Rectilinear planar layouts and bipolar orientations of planar graphs
• On mixed linear layouts of series-parallel graphs
• Parameterized algorithms for linear layouts of graphs with respect to the vertex cover number
• The mixed page number of graphs
• Mixed linear layouts: complexity, heuristics, and experiments
• Lazy queue layouts of posets
• Parameterized Algorithms for Queue Layouts
• Lazy Queue Layouts of Posets
• On Mixed Linear Layouts of Series-Parallel Graphs
• Parameterized algorithms for queue layouts
• Planar graphs of bounded degree have bounded queue number
• Graph Drawing
• Queue layouts of planar 3-trees
• Queue layouts of planar 3-trees
• Linear layouts of bipartite planar graphs
• On families of planar DAGs with constant stack number
• Vertex-bipartition: a unified approach for kernelization of graph linear layout problems parameterized by vertex cover
• Directed acyclic outerplanar graphs have constant stack number
• Forbidden patterns in mixed linear layouts
• Transforming stacks into queues: mixed and separated layouts of graphs
• Linear layouts of graphs with priority queues

This page was built for publication: Mixed linear layouts of planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625112)