A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width

For every fixed surface S, orientable or non-orientable, and a given graph G, Mohar (STOC'96 and Siam J. Discrete Math. (1999)) described a linear time algorithm which yields either an embedding of G in S or a minor of G which is not embeddable in S and is minimal with this property. That algorithm, however, needs a lot of lemmas which spanned six additional papers. In this paper, we give a new linear time algorithm for the same problem. The advantages of our algorithm are the following: 1. The proof is considerably simpler: it needs only about 10 pages, and some results (with rather accessible proofs) from graph minors theory, while Mohar's original algorithm and its proof occupy more than 100 pages in total. 2. The hidden constant (depending on the genus g of the surface S) is much smaller. It is singly exponential in g, while it is doubly exponential in Mohar's algorithm. As a spinoff of our main result, we give another linear time algorithm, which is of independent interest. This algorithm computes the genus and constructs minimum genus embeddings of graphs of bounded tree-width. This resolves a conjecture by Neil Robertson and solves one of the most annoying long standing open question about complexity of algorithms on graphs of bounded tree-width.

Authors

• Ken-ichi Kawarabayashi
• Bojan Mohar
• Bruce A. Reed

Keywords

• Tree graphs
• Testing
• Polynomials
• Graph theory
• Computer science
• Informatics
• Cyclic redundancy check
• Mathematics
• Embedded computing
• Very large scale integration
• Linear Time
• Linear Algorithm
• Linear-time Algorithm
• Algorithm For Problem
• Time Constant
• Isomorphism
• Results In Areas
• Rotation System
• Theoretical Interest
• Vertex Degree
• Joining Tree
• Private Communication
• Planar Graphs
• Class Of Graphs
• Subset Of Vertices
• Expensive Part
• Family Of Graphs
• Linear time algorithm
• Embedding
• Surface
• Genus of a graph
• Tree-width