Recognizing hyperelliptic graphs in polynomial time
Publication date
2018-01-01
Authors
Bodewes, Jelco M.
Bodlaender, H.L.
Cornelissen, Gunther
Wegen, Marieke van der
Editors
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
unspecified
Abstract
Based on analogies between algebraic curves and graphs, Baker and Norine introduced divisorial gonality, a graph parameter for multigraphs related to treewidth, multigraph algorithms and number theory. We consider so-called hyperelliptic graphs (multigraphs of gonality 2) and provide a safe and complete set of reduction rules for such multigraphs, showing that we can recognize hyperelliptic graphs in time O(n log n+ m), where n is the number of vertices and m the number of edges of the multigraph. A corollary is that we can decide with the same runtime whether a two-edge-connected graph G admits an involution σ such that the quotient G/ ⟨ σ⟩ is a tree.
Keywords
Taverne, Theoretical Computer Science, General Computer Science
Citation
Bodewes, J M, Bodlaender, H L, Cornelissen, G & van der Wegen, M 2018, Recognizing hyperelliptic graphs in polynomial time. in Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11159 LNCS, Springer, pp. 52-64, 44th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2018, Cottbus, Germany, 27/06/18. https://doi.org/10.1007/978-3-030-00256-5_5, conference