Characterizing Planarity by the Splittable Deque

Auer, Christopher and Brandenburg, Franz J. and Gleißner, Andreas and Hanauer, Kathrin (2013) Characterizing Planarity by the Splittable Deque. In: 21st International Symposium, GD 2013, September 23-25, 2013 , pp. 25-36(Official URL:

Full text not available from this repository.


A graph layout describes the processing of a graph G by a data structure , and the graph is called a  -graph. The vertices of G are totally ordered in a linear layout and the edges are stored and organized in  . At each vertex, all edges to predecessors in the linear layout are removed and all edges to successors are inserted. There are intriguing relationships between well-known data structures and classes of planar graphs: The stack graphs are the outerplanar graphs [4], the queue graphs are the arched leveled-planar graphs [12], the 2-stack graphs are the subgraphs of planar graphs with a Hamilton cycle [4], and the deque graphs are the subgraphs of planar graphs with a Hamilton path [2]. All of these are proper subclasses of the planar graphs, even for maximal planar graphs. We introduce splittable deques as a data structure to capture planarity. A splittable deque is a deque which can be split into sub-deques. The splittable deque provides a new insight into planarity testing by a game on switching trains. Here, we use it for a linear-time planarity test of a given rotation system.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.770 Planarity Testing

Actions (login required)

View Item View Item