Characterizing Planarity by the Splittable Deque
| Autor: | Andreas Gleiβner, Christopher Auer, Kathrin Hanauer, Franz J. Brandenburg |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Discrete mathematics
Clique-sum Book embedding Dense graph Computer Science::Computational Geometry 1-planar graph Planar graph Combinatorics Indifference graph symbols.namesake Pathwidth Chordal graph TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY symbols Computer Science::Distributed Parallel and Cluster Computing MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Graph Drawing ISBN: 9783319038407 Graph Drawing |
| DOI: | 10.1007/978-3-319-03841-4_3 |
| Popis: | A graph layout describes the processing of a graph G by a data structure $\mathcal{D}$ , and the graph is called a $\mathcal{D}$ -graph. The vertices of G are totally ordered in a linear layout and the edges are stored and organized in $\mathcal{D}$ . 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|