Michael A. Bekos
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
Research Subjects
Research Interests
Michael A. Bekos has a total of 124 co-authors. Here are the top co-authors by number of shared publications:
Michael Kaufmann
42 shared publications- Antonios Symvonis
National Technical University of Athens, Athens, Greece
35 shared publications - Fabrizio Montecchiani
University of Perugia, Perugia, Italy
18 shared publications - Michael Kaufmann
Universität Tübingen
17 shared publications - Martin Gronemann
TU Wien
16 shared publications - Chrysanthi N. Raftopoulou
NTUA, Sch Appl Math & Phys Sci, Athens, Greece
14 shared publications
Latest Publications
- Open Access
- 9 February 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1069
Weakly leveled planarity with bounded span
- 9 February 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1069
Open AccessWeakly leveled planarity with bounded span
- Open Access
- 17 October 2025
- Published by Elsevier in Theoretical Computer Science
- Vol. 1058
Drawing graphs with k vertices per face: Complexity and algorithms
- 17 October 2025
- Published by Elsevier in Theoretical Computer Science
- Vol. 1058
Open AccessDrawing graphs with k vertices per face: Complexity and algorithms
- Open Access
- 13 October 2025
- Published by Journal of Graph Algorithms and Applications in Journal of Graph Algorithms and Applications
- Vol. 29 (3) , 1-22
On k-planar Graphs without Short Cycles
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.
- 13 October 2025
- Published by Journal of Graph Algorithms and Applications in Journal of Graph Algorithms and Applications
- Vol. 29 (3) , 1-22
Open AccessOn k-planar Graphs without Short Cycles
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
- 3 October 2024
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 31 (4) , P4.56
Graph Product Structure for $h$-Framed Graphs
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.- 3 October 2024
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 31 (4) , P4.56
Open AccessGraph Product Structure for $h$-Framed Graphs
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
- 17 May 2024
- Published by Journal of Graph Algorithms and Applications in Journal of Graph Algorithms and Applications
- Vol. 28 (2)
Guest Editors' Foreword
Special Issue on GD 2023: Guest Editors' Foreword
- 17 May 2024
- Published by Journal of Graph Algorithms and Applications in Journal of Graph Algorithms and Applications
- Vol. 28 (2)
Open AccessGuest Editors' Foreword
Special Issue on GD 2023: Guest Editors' Foreword
- Open Access
- 27 October 2023
- Published by Springer Nature in Algorithmica
- Vol. 86 (2) , 613-637
Recognizing Map Graphs of Bounded Treewidth
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.
- 27 October 2023
- Published by Springer Nature in Algorithmica
- Vol. 86 (2) , 613-637
Open AccessRecognizing Map Graphs of Bounded Treewidth
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
- 11 September 2023
- Published by Elsevier in Discrete Mathematics
- Vol. 347 (1)
Book embeddings of k-framed graphs and k-map graphs
- 11 September 2023
- Published by Elsevier in Discrete Mathematics
- Vol. 347 (1)
Open AccessBook embeddings of k-framed graphs and k-map graphs
- Open Access
On the Deque and Rique Numbers of Complete and Complete Bipartite Graphs
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 AccessOn the Deque and Rique Numbers of Complete and Complete Bipartite Graphs
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
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 AccessAn Online Framework to Interact and Efficiently Compute Linear Layouts of Graphs
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
- 11 March 2023
- Published by Springer Nature in Algorithmica
- Vol. 85 (9) , 2667-2692
Bitonic st-Orderings for Upward Planar Graphs: Splits and Bends in the Variable Embedding Scenario
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$$ . 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$$ 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$$ 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.- 11 March 2023
- Published by Springer Nature in Algorithmica
- Vol. 85 (9) , 2667-2692
Open AccessBitonic st-Orderings for Upward Planar Graphs: Splits and Bends in the Variable Embedding Scenario
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$$ . 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$$ 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$$ 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.