Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem

Walter Didimo, Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Stephen Kobourov, Marie Diana Sieper

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A vertex of a plane digraph is bimodal if all its incoming edges (and hence all its outgoing edges) are consecutive in the cyclic order around it. A plane digraph is bimodal if all its vertices are bimodal. Bimodality is at the heart of many types of graph layouts, such as upward drawings, level-planar drawings, and L-drawings. If the graph is not bimodal, the Maximum Bimodal Subgraph (MBS) problem asks for an embedding-preserving bimodal subgraph with the maximum number of edges. We initiate the study of the MBS problem from the parameterized complexity perspective with two main results: (i) we describe an FPT algorithm parameterized by the branchwidth (and hence by the treewidth) of the graph; (ii) we establish that MBS parameterized by the number of non-bimodal vertices admits a polynomial kernel. As the byproduct of these results, we obtain a subexponential FPT algorithm and an efficient polynomial-time approximation scheme for MBS.

Original languageEnglish (US)
Title of host publicationGraph Drawing and Network Visualization - 31st International Symposium, GD 2023, Revised Selected Papers
EditorsMichael A. Bekos, Markus Chimani
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages14
ISBN (Print)9783031492747
StatePublished - 2023
Externally publishedYes
Event31st International Symposium on Graph Drawing and Network Visualization, GD 2023 - Palermo, Italy
Duration: Sep 20 2023Sep 22 2023

Publication series

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


Conference31st International Symposium on Graph Drawing and Network Visualization, GD 2023


  • FPT algorithms
  • approximation scheme
  • bimodal graphs
  • maximum bimodal subgraph
  • parameterized complexity
  • polynomial kernel

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem'. Together they form a unique fingerprint.

Cite this