Recognizing hyperelliptic graphs in polynomial time

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)


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(nlog 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.

Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings
EditorsAndreas Brandstädt, Ekkehard Köhler, Klaus Meer
Place of PublicationCham
Number of pages13
ISBN (Electronic)978-3-030-00256-5
ISBN (Print)978-3-030-00255-8
Publication statusPublished - 1 Jan 2018
Event44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018) - Cottbus, Germany
Duration: 27 Jun 201829 Jun 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11159 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018)
Abbreviated titleWG2018
Internet address


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

Cite this