## Characterizing Planarity by the Splittable Deque
Auer, Christopher and Brandenburg, Franz J. and Gleißner, Andreas and Hanauer, Kathrin
(2013)
Full text not available from this repository. ## AbstractA 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.
Repository Staff Only: item control page References |