Recognizing hyperelliptic graphs in polynomial time

Jelco M. Bodewes, Hans L. Bodlaender, Gunther Cornelissen, Marieke van der Wegen

Research output: Contribution to journalArticleAcademic

125 Downloads (Pure)


Recently, a new set of multigraph parameters was defined, called "gonalities". Gonality bears some similarity to treewidth, and is a relevant graph parameter for problems in number theory and multigraph algorithms. Multigraphs of gonality 1 are trees. We consider so-called "hyperelliptic graphs" (multigraphs of gonality 2) and provide a safe and complete sets of reduction rules for such multigraphs, showing that for three of the flavors of gonality, we can recognize hyperelliptic graphs in O(n log n+m) time, where n is the number of vertices and m the number of edges of the multigraph.
Original languageEnglish
Article number1706.06570v1
Number of pages34
Publication statusPublished - 18 Jun 2017

Bibliographical note

33 pages, 8 figures


Dive into the research topics of 'Recognizing hyperelliptic graphs in polynomial time'. Together they form a unique fingerprint.

Cite this