EUVIMEDEUVIMED entdecken
Crossref

Planar Graphs Have Bounded Queue-Number

Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood

Journal of the ACM · 31.08.2020 · 67 (4) · 1-38

DOI: 10.1145/3385731 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 06.08.2020. Verfasst von Vida Dujmović und 5 weiteren Autor:innen. Die Arbeit wurde bisher 69-mal zitiert (Crossref) und nennt 115 Literaturangaben. Gefördert von: Polish National Science Center, Australian Research Council, Natural Sciences and Engineering Research Council of Canada.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • Polish National Science Center
  • Australian Research Council
  • Natural Sciences and Engineering Research Council of Canada
  • Wallonia-Brussels Federation

Zitieren

APA

Dujmović, V., Joret, G., Micek, P., Morin, P., Ueckerdt, T., & Wood, D. R. (2020). Planar Graphs Have Bounded Queue-Number. Journal of the ACM, 67(4), 1-38. https://doi.org/10.1145/3385731

Vancouver

Dujmović V, Joret G, Micek P, Morin P, Ueckerdt T, Wood DR. Planar Graphs Have Bounded Queue-Number. Journal of the ACM. 2020;67(4):1-38. doi:10.1145/3385731

BibTeX
@article{Dujmovi2020,
  author = {Dujmović, Vida and Joret, Gwenaël and Micek, Piotr and Morin, Pat and Ueckerdt, Torsten and Wood, David R.},
  title = {Planar Graphs Have Bounded Queue-Number},
  journal = {Journal of the ACM},
  year = {2020},
  volume = {67},
  number = {4},
  pages = {1--38},
  doi = {10.1145/3385731}
}
Kostenlos starten →