### 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 language | English |
---|---|

Title of host publication | Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings |

Editors | Andreas Brandstädt, Ekkehard Köhler, Klaus Meer |

Place of Publication | Cham |

Publisher | Springer |

Pages | 52-64 |

Number of pages | 13 |

ISBN (Electronic) | 978-3-030-00256-5 |

ISBN (Print) | 978-3-030-00255-8 |

DOIs | |

Publication status | Published - 1 Jan 2018 |

Event | 44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018) - Cottbus, Germany Duration: 27 Jun 2018 → 29 Jun 2018 https://www.wg2018.b-tu.de/ |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 11159 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018) |
---|---|

Abbreviated title | WG2018 |

Country | Germany |

City | Cottbus |

Period | 27/06/18 → 29/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

*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