Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
From MaRDI portal
Publication:4875441
DOI10.1137/S0895480194272183zbMath0847.05046OpenAlexW1974876810MaRDI QIDQ4875441
Lyudmil Aleksandrov, Hristo N. Djidjev
Publication date: 29 September 1996
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895480194272183
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond ⋮ Minimum Cuts in Surface Graphs ⋮ Graph separators: A parameterized view ⋮ Planar and Toroidal Morphs Made Easier ⋮ Collective tree spanners in graphs with bounded parameters ⋮ Planar and toroidal morphs made easier ⋮ Algorithms for approximate shortest path queries on weighted polyhedral surfaces ⋮ Layered separators in minor-closed graph classes with applications ⋮ Three problems about simple polygons ⋮ Counting models for 2SAT and 3SAT formulae ⋮ General lower bounds for the minor crossing number of graphs ⋮ Succinct and Implicit Data Structures for Computational Geometry ⋮ An external memory data structure for shortest path queries ⋮ Short and Simple Cycle Separators in Planar Graphs
