MBMichael A. Bekos

Michael A. Bekos

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Michael A. Bekos has a total of 124 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Weakly leveled planarity with bounded span

    by Michael A. Bekos, Giordano Da Lozzo, Fabrizio Frati, Siddharth Gupta, Philipp Kindermann, Giuseppe Liotta, Ignaz Rutter, Ioannis G. Tollis

  • Open Access

    Drawing graphs with k vertices per face: Complexity and algorithms

    by Michael A. Bekos, Giuseppe Di Battista, Emilio Di Giacomo, Walter Didimo, Michael Kaufmann, Fabrizio Montecchiani

  • Open Access

    On k-planar Graphs without Short Cycles

    by Michael A. Bekos, Prosenjit Bose, Aaron Büngener, Vida Dujmovi´c, Michael Hoffmann, Michael Kaufmann, Pat Morin, Saeed Odak, Alexandra Weinberger

    We study the impact of forbidding short cycles to the edge density of k-planar graphs; a k-planar graph is one that can be drawn in the plane with at most k crossings per edge. Specifically, we consider three settings, according to which the forbidden substructures are 3-cycles, 4-cycles or both of them (i.e., girth ≥ 5). For all three settings and all k ∈ {1,2,3}, we present lower and upper bounds on the maximum number of edges in any k-planar graph on n vertices. Our bounds are of the form c\sqrt{k}n, for some explicit constant c that depends on k and on the setting. For general k ≥ 4 our bounds are of the form c\sqrt{k}n, for some explicit constant c. These results are obtained by leveraging different techniques, such as the discharging method, the recently introduced density formula for non-planar graphs, and new upper bounds for the crossing number of 2-- and 3-planar graphs in combination with corresponding lower bounds based on the Crossing Lemma.


  • Open Access

    Graph Product Structure for $h$-Framed Graphs

    by Michael A. Bekos, Giordano Da Lozzo, Petr Hliněný, Michael Kaufmann

    Graph product structure theory expresses certain graphs as subgraphs of the strong product of much simpler graphs. In particular, an elegant formulation for the corresponding structural theorems involves the strong product of a path and of a bounded treewidth graph, and allows to lift combinatorial results for bounded treewidth graphs to graph classes for which the product structure holds, such as to planar graphs [Dujmović et al., J. ACM, 67(4), 22:1-38, 2020]. In this paper, we join the search for extensions of this powerful tool beyond planarity by considering the $h$-framed graphs, a graph class that includes $1$-planar, optimal $2$-planar, and $k$-map graphs (for appropriate values of $h$). We establish a graph product structure theorem for $h$-framed graphs stating that the graphs in this class are subgraphs of the strong product of a path, of a planar graph of treewidth at most $3$, and of a clique of size $3\lfloor \frac{h}{2}\rfloor + \lfloor \frac{h}{3}\rfloor -1$. This allows us to improve over the previous structural theorems for $1$-planar and $k$-map graphs. Our results lead to significant progress over the previous bounds on the queue number, non-repetitive chromatic number, and $p$-centered chromatic number of these graph classes, e.g., we lower the currently best upper bound on the queue number of $1$-planar graphs and $k$-map graphs from $115$ to $82$ and from $\lfloor \frac{33}{2}(k+3\lfloor \frac{k}{2}\rfloor -3)\rfloor$ to $\lfloor \frac{33}{2}(3\lfloor \frac{k}{2}\rfloor + \lfloor \frac{k}{3}\rfloor -1)\rfloor$, respectively. We also employ the product structure machinery to improve the current upper bounds on the twin-width of $1$-planar graphs from $O(1)$ to $72$. All our structural results are constructive and yield efficient algorithms to obtain the corresponding decompositions.


  • Open Access

    Guest Editors' Foreword

    by Michael A. Bekos, Markus Chimani

    Special Issue on GD 2023: Guest Editors' Foreword

  • Open Access

    Recognizing Map Graphs of Bounded Treewidth

    by Patrizio Angelini, Michael A. Bekos, Giordano Da Lozzo, Martin Gronemann, Fabrizio Montecchiani, Alessandra Tappini

    A map is a partition of the sphere into interior-disjoint regions homeomorphic to closed disks. Some regions are labeled as nations, while the remaining ones are labeled as holes. A map in which at mostknations touch at the same point is ak-map, while it is hole-free if it contains no holes. A graph is a map graph if there is a bijection between its vertices and the nations of a map, such that two nations touch if and only the corresponding vertices are connected by an edge. We present a fixed-parameter tractable algorithm for recognizing map graphs parameterized by treewidth. Its time complexity is linear in the size of the graph. It reports a certificate in the form of a so-called witness, if the input is a yes-instance. Our algorithmic framework is general enough to test, for anyk, if the input graph admits ak-map or a hole-free k-map.


  • Open Access

    Book embeddings of k-framed graphs and k-map graphs

    by Michael A. Bekos, Giordano Da Lozzo, Svenja M. Griesbach, Martin Gronemann, Fabrizio Montecchiani, Chrysanthi Raftopoulou


  • Open Access

    On the Deque and Rique Numbers of Complete and Complete Bipartite Graphs

    by Michael A. Bekos, Michael Kaufmann, Maria Eleni Pavlidi, Xenia Rieger

    Several types of linear layouts of graphs are obtained by leveraging known data structures; the most notable representatives are the stack and the queue layouts. In this content, given a data structure, one seeks to specify an order of the vertices of the graph and a partition of its edges into pages, such that the endpoints of the edges assigned to each page can be processed by the given data structure in the underlying order. In this paper, we study deque and rique layouts of graphs obtained by leveraging the double-ended queue and the restricted-input double-ended queue (or deque and rique, for short), respectively. Hence, they generalize both the stack and the queue layouts. We focus on complete and complete bipartite graphs and present bounds on their deque- and rique-numbers, that is, on the minimum number of pages needed by any of these two types of linear layouts.

  • Open Access

    An Online Framework to Interact and Efficiently Compute Linear Layouts of Graphs

    by Michael A. Bekos, Mirco Haug, Michael Kaufmann, Julia Männecke

    We present a prototype online system to automate the procedure of computing different types of linear layouts of graphs under different user-specific constraints. Currently, four different types of linear layouts are supported: stack, queue, rique and deque, as well as, any mixture of them. The system consists of two main components; the client and the server sides. The client side is built upon an easy-to-use editor, which supports basic interaction with graphs, enriched with several additional features to allow the user to define and further constraint the linear layout to be computed. The server side, which is available to multiple clients through a well-documented API, is responsible for the actual computation of the linear layout. Its algorithmic core is an extension of a SAT formulation that is known to be robust enough to solve non-trivial instances in reasonable amount of time.

  • Open Access

    Bitonic st-Orderings for Upward Planar Graphs: Splits and Bends in the Variable Embedding Scenario

    by Patrizio Angelini, Michael A. Bekos, Henry Förster, Martin Gronemann

    Bitonic st-orderings for st-planar graphs were introduced as a method to cope with several graph drawing problems. Notably, they have been used to obtain the best-known upper bound on the number of bends for upward planar polyline drawings with at most one bend per edge in polynomial area. For an st-planar graph that does not admit a bitonic st-ordering, one may split certain edges such that for the resulting graph such an ordering exists. Since each split is interpreted as a bend, one is usually interested in splitting as few edges as possible. While this optimization problem admits a linear-time algorithm in the fixed embedding setting, it remains open in the variable embedding setting. We close this gap in the literature by providing a linear-time algorithm that optimizes over all embeddings of the input st-planar graph. The best-known lower bound on the number of required splits of an st-planar graph with n vertices is $$n-3$$ n - 3 . However, it is possible to compute a bitonic st-ordering without any split for the st-planar graph obtained by reversing the orientation of all edges. In terms of upward planar polyline drawings in polynomial area, the former translates into $$n-3$$ n - 3 bends, while the latter into no bends. We show that this idea cannot always be exploited by describing an st-planar graph that needs at least $$n-5$$ n - 5 splits in both orientations. We provide analogous bounds for graphs with small degree. Finally, we further investigate the relationship between splits in bitonic st-orderings and bends in upward planar polyline drawings with polynomial area, by providing bounds on the number of bends in such drawings.