Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus

DOI10.1137/S0895480194272183MaRDI QIDQ4875441zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

surfacesseparatorspartitioninggraphic algorithmsembedded graphsbounded genus

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• scientific article; zbMATH DE number 3946182
• A separator theorem for graphs of bounded genus
• scientific article; zbMATH DE number 3970774
• Edge separators for graphs of bounded genus with applications
• scientific article; zbMATH DE number 219242

Cited in

(27)

• An external memory data structure for shortest path queries
• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• Counting models for 2SAT and 3SAT formulae
• Edge separators for graphs of bounded genus with applications
• scientific article; zbMATH DE number 4117852 (Why is no real title available?)
• Algorithms for approximate shortest path queries on weighted polyhedral surfaces
• Graph separators: A parameterized view
• Surface split decompositions and subgraph isomorphism in graphs on surfaces
• Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• scientific article; zbMATH DE number 512923 (Why is no real title available?)
• Planar and toroidal morphs made easier
• General lower bounds for the minor crossing number of graphs
• Three problems about simple polygons
• scientific article; zbMATH DE number 3970774 (Why is no real title available?)
• Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus
• Layered separators in minor-closed graph classes with applications
• scientific article; zbMATH DE number 3946182 (Why is no real title available?)
• Succinct and Implicit Data Structures for Computational Geometry
• Short and simple cycle separators in planar graphs
• scientific article; zbMATH DE number 2079390 (Why is no real title available?)
• Planar and Toroidal Morphs Made Easier
• Collective tree spanners in graphs with bounded parameters
• Minimum Cuts in Surface Graphs
• scientific article; zbMATH DE number 4195959 (Why is no real title available?)
• A separator theorem for graphs of bounded genus
• scientific article; zbMATH DE number 219242 (Why is no real title available?)

This page was built for publication: Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4875441)