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

4 Citations (Scopus)

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(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
PublisherSpringer
Pages52-64
Number of pages13
ISBN (Electronic)978-3-030-00256-5
ISBN (Print)978-3-030-00255-8
DOIs
Publication statusPublished - 1 Jan 2018
Event44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018) - Cottbus, Germany
Duration: 27 Jun 201829 Jun 2018
https://www.wg2018.b-tu.de/

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

Conference

Conference44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018)
Abbreviated titleWG2018
CountryGermany
CityCottbus
Period27/06/1829/06/18
Internet address

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

  • Cite this

    Bodewes, J. M., Bodlaender, H. L., Cornelissen, G., & van der Wegen, M. (2018). Recognizing hyperelliptic graphs in polynomial time. In A. Brandstädt, E. Köhler, & K. Meer (Eds.), Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings (pp. 52-64). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11159 LNCS). Springer. https://doi.org/10.1007/978-3-030-00256-5_5