2005/02/16 by Erik D. Demaine, Demaine, Erik D., MohammadTaghi Hajiaghayi +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0502070
12 pages
arxiv created 2005/02/16 · openalex publication_date 2005/02/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we extend the theory of bidimensionality to two families of graphs that do not exclude fixed minors: map graphs and power graphs. In both cases we prove a polynomial relation between the treewidth of a graph in the family and the size of the largest grid minor. These bounds improve the running times of a broad class of fixed-parameter algorithms. Our novel technique of using approximate max-min relations between treewidth and size of grid minors is powerful, and we show how it can also be used, e.g., to prove a linear relation between the treewidth of a bounded-genus graph and the treewidth of its dual.