Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs

DOI10.1007/978-3-662-43948-7_41zbMath1416.05224arXiv1402.3774OpenAlexW2963801092WikidataQ62048080 ScholiaQ62048080MaRDI QIDQ5167767

Jan Kratochvíl, Jiří Fiala, Roman Nedela, Pavel Klavík

Publication date: 1 July 2014

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.3774

zbMATH Keywords

regular covers for 2-cuts

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

\(\mathcal{IV}\)-matching is strongly \textsf{NP}-hard ⋮ 3-connected reduction for regular graph covers ⋮ List covering of regular multigraphs ⋮ Jordan-like characterization of automorphism groups of planar graphs ⋮ List covering of regular multigraphs with semi-edges ⋮ Computational complexity of covering three-vertex multigraphs ⋮ Graph isomorphism restricted by lists

This page was built for publication: Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs