Planar graphs have bounded queue-number
| Autor: | Vida Dujmović, David R. Wood, Pat Morin, Torsten Ueckerdt, Piotr Micek, Gwenaël Joret |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Quotient graph Combinatorics symbols.namesake Queue number Artificial Intelligence TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Informatique mathématique FOS: Mathematics 0202 electrical engineering electronic engineering information engineering Graph minor Théorie des graphes Mathematics - Combinatorics 0101 mathematics Mathematics Apex graph 010102 general mathematics Graph theory Planar graph Treewidth Hardware and Architecture Control and Systems Engineering 010201 computation theory & mathematics Bounded function symbols 020201 artificial intelligence & image processing Combinatorics (math.CO) Software Graph product Information Systems MathematicsofComputing_DISCRETEMATHEMATICS Computer Science - Discrete Mathematics |
| Zdroj: | FOCS Annual Symposium on Foundations of Computer Science, FOCS 2019 Journal of the Association for Computing Machinery, 67 (4 |
| Popis: | We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath et al. [66] from 1992. The key to the proof is a new structural tool called layered partitions , and the result that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number. Layered partitions have strong connections to other topics, including the following two examples. First, they can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes. Second, we give a simple proof of the result by DeVos et al. [31] that graphs in a proper minor-closed class have low treewidth colourings. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|