Characterizing Planarity by the Splittable DequeAuer, 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 2325, 2013 , pp. 2536(Official URL: http://dx.doi.org/10.1007/9783319038414_3). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319038414_3
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 wellknown data structures and classes of planar graphs: The stack graphs are the outerplanar graphs [4], the queue graphs are the arched leveledplanar graphs [12], the 2stack 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 subdeques. The splittable deque provides a new insight into planarity testing by a game on switching trains. Here, we use it for a lineartime planarity test of a given rotation system.
Actions (login required)
