@inproceedings{cc62113bb82546798aa2fa4bda2a645a,

title = "Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem",

abstract = "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.",

keywords = "FPT algorithms, approximation scheme, bimodal graphs, maximum bimodal subgraph, parameterized complexity, polynomial kernel",

author = "Walter Didimo and Fomin, {Fedor V.} and Golovach, {Petr A.} and Tanmay Inamdar and Stephen Kobourov and Sieper, {Marie Diana}",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 31st International Symposium on Graph Drawing and Network Visualization, GD 2023 ; Conference date: 20-09-2023 Through 22-09-2023",

year = "2023",

doi = "10.1007/978-3-031-49275-4_13",

language = "English (US)",

isbn = "9783031492747",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "189--202",

editor = "Bekos, {Michael A.} and Markus Chimani",

booktitle = "Graph Drawing and Network Visualization - 31st International Symposium, GD 2023, Revised Selected Papers",

address = "Germany",

}