Testing Planarity by Switching Trains

Auer, Christopher and Gleißner, Andreas and Hanauer, Kathrin and Vetter, Sebastian (2013) Testing Planarity by Switching Trains. In: 20th International Symposium, GD 2012, September 19-21, 2012 , pp. 557-558(Official URL: http://link.springer.com/chapter/10.1007/978-3-642...).

Full text not available from this repository.


We show that planarity testing can be interpreted as a train switching problem. Train switching problems have been studied in the context of permutation networks, i. e., permuting the cars of a train on a given railroad network [5]. The cars enter the network one at a time, some are stored temporarily in the network and the cars leave the network in the prescribed permutation. For the planarity test we use the metaphor of train switching in the context of graph layouts. In a graph layout the vertices are processed according to a total order, i. e., an ordering of the vertices, which is called linear layout. The edges are data items that are inserted to and removed from a given data structure. The vertices are processed in the order of the linear layout. At each vertex, at first all edges incident to preceding vertices are removed from the data structure and then all edges incident to succeeding vertices are inserted into the data structure. These operations must obey the principles of the underlying data structure, such as “LIFO” for a stack or “FIFO” for a queue. A graph G is a stack graph, i. e., has a stack layout, if and only if it is outerplanar, and it is a 2-stack graph if and only if it is a subgraph of a planar graph with a Hamiltonian cycle [3].

Item Type: Conference Poster
Additional Information: 10.1007/978-3-642-36763-2_51
Classifications: G Algorithms and Complexity > G.770 Planarity Testing
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1344

Actions (login required)

View Item View Item