Chrysanthi N. Raftopoulou
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
Chrysanthi N. Raftopoulou has a total of 36 co-authors. Here are the top co-authors by number of shared publications:
- Michael A. Bekos
University of Ioannina
14 shared publications - Fabrizio Montecchiani
University of Perugia, Perugia, Italy
7 shared publications - Martin Gronemann
TU Wien
7 shared publications - Giordano Da Lozzo
Roma Tre University, Rome, Italy
5 shared publications Michael Kaufmann
Wilhelm-Schickhard-Institut für Informatik Universität Tübingen Tübingen Germany
5 shared publications- Fabrizio Frati
Roma Tre University, Rome, Italy
4 shared publications
Latest Publications
- 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
- 19 January 2023
- Published by Springer Nature
- p. 361-370
Recognizing DAGs with Page-Number 2 Is NP-complete
- 19 January 2023
- Published by Springer Nature
- p. 361-370
Recognizing DAGs with Page-Number 2 Is NP-complete
- Open Access
- 11 January 2023
- Published by Elsevier in Theoretical Computer Science
- Vol. 946
Recognizing DAGs with page-number 2 is NP-complete
- 11 January 2023
- Published by Elsevier in Theoretical Computer Science
- Vol. 946
Open AccessRecognizing DAGs with page-number 2 is NP-complete
- Open Access
Recognizing DAGs with Page-Number 2 is NP-complete
The page-number of a directed acyclic graph (a DAG, for short) is the minimum $k$ for which the DAG has a topological order and a $k$-coloring of its edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological order. In 1999, Heath and Pemmaraju conjectured that the recognition of DAGs with page-number $2$ is NP-complete and proved that recognizing DAGs with page-number $6$ is NP-complete [SIAM J. Computing, 1999]. Binucci et al. recently strengthened this result by proving that recognizing DAGs with page-number $k$ is NP-complete, for every $k\geq 3$ [SoCG 2019]. In this paper, we finally resolve Heath and Pemmaraju's conjecture in the affirmative. In particular, our NP-completeness result holds even for $st$-planar graphs and planar posets.Open AccessRecognizing DAGs with Page-Number 2 is NP-complete
The page-number of a directed acyclic graph (a DAG, for short) is the minimum $k$ for which the DAG has a topological order and a $k$-coloring of its edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological order. In 1999, Heath and Pemmaraju conjectured that the recognition of DAGs with page-number $2$ is NP-complete and proved that recognizing DAGs with page-number $6$ is NP-complete [SIAM J. Computing, 1999]. Binucci et al. recently strengthened this result by proving that recognizing DAGs with page-number $k$ is NP-complete, for every $k\geq 3$ [SoCG 2019]. In this paper, we finally resolve Heath and Pemmaraju's conjecture in the affirmative. In particular, our NP-completeness result holds even for $st$-planar graphs and planar posets. - Open Access
- 28 September 2022
- Published by Springer Nature in Algorithmica
- Vol. 85 (2) , 544-562
An Improved Upper Bound on the Queue Number of Planar Graphs
Ak-queue layout is a special type of a linear layout, in which the linear order avoids $$(k+1)$$ -rainbows, that is, $$k+1$$ independent edges that pairwise form a nested pair. The optimization goal is to determine thequeue numberof a graph, which is defined as the minimum value ofkfor which ak-queue layout is feasible. Recently, Dujmović et al. [J. ACM, 67(4), 22:1–38, 2020] showed that the queue number of planar graphs is at most 49, thus settling in the positive a long-standing conjecture by Heath, Leighton and Rosenberg. To achieve this breakthrough result, their approach involves three different techniques: (1) an algorithm to obtain 2-queue layouts of outerplanar graphs, (2) an algorithm to obtain 5-queue layouts of planar 3-trees, and (3) a decomposition of a planar graph into so-called tripods. In this work, we push further each of these techniques to obtain the first non-trivial improvement of the upper bound on the queue number of planar graphs from 49 to $$42 $$ .- 28 September 2022
- Published by Springer Nature in Algorithmica
- Vol. 85 (2) , 544-562
Open AccessAn Improved Upper Bound on the Queue Number of Planar Graphs
Ak-queue layout is a special type of a linear layout, in which the linear order avoids $$(k+1)$$ -rainbows, that is, $$k+1$$ independent edges that pairwise form a nested pair. The optimization goal is to determine thequeue numberof a graph, which is defined as the minimum value ofkfor which ak-queue layout is feasible. Recently, Dujmović et al. [J. ACM, 67(4), 22:1–38, 2020] showed that the queue number of planar graphs is at most 49, thus settling in the positive a long-standing conjecture by Heath, Leighton and Rosenberg. To achieve this breakthrough result, their approach involves three different techniques: (1) an algorithm to obtain 2-queue layouts of outerplanar graphs, (2) an algorithm to obtain 5-queue layouts of planar 3-trees, and (3) a decomposition of a planar graph into so-called tripods. In this work, we push further each of these techniques to obtain the first non-trivial improvement of the upper bound on the queue number of planar graphs from 49 to $$42 $$ . - Open Access
Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages
An embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. For planar graphs, a fundamental result is due to Yannakakis, who proposed an algorithm to compute embeddings of planar graphs in books with four pages. Our main contribution is a technique that generalizes this result to a much wider family of nonplanar graphs, which is characterized by a biconnected skeleton of crossing-free edges whose faces have bounded degree. Notably, this family includes all 1-planar, all optimal 2-planar, and all k-map (with bounded k) graphs as subgraphs. We prove that this family of graphs has bounded book thickness, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal 2-planar and k-map graphs.
Open AccessBook Embeddings of Nonplanar Graphs with Small Faces in Few Pages
An embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. For planar graphs, a fundamental result is due to Yannakakis, who proposed an algorithm to compute embeddings of planar graphs in books with four pages. Our main contribution is a technique that generalizes this result to a much wider family of nonplanar graphs, which is characterized by a biconnected skeleton of crossing-free edges whose faces have bounded degree. Notably, this family includes all 1-planar, all optimal 2-planar, and all k-map (with bounded k) graphs as subgraphs. We prove that this family of graphs has bounded book thickness, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal 2-planar and k-map graphs.
- 23 December 2021
- Published by Springer Nature
- p. 87-100
Recognizing and Embedding Simple Optimal 2-Planar Graphs
- 23 December 2021
- Published by Springer Nature
- p. 87-100
Recognizing and Embedding Simple Optimal 2-Planar Graphs