Linear layouts of graphs form an important methodological tool studied in various contexts. In essence, given a graph, the objective is to determine an ordering of the vertices and partition the edges into the minimum possible number of sets (called pages), such that the edges in each page avoid specific patterns. Among the many variants of linear layouts studied in this field of research, the following are the most studied ones:

  • book embeddings, in which no two independent edges of the same page can cross.
  • queue layouts, which disallow independent edges to nest.
  • mixed linear layouts, which impose different restrictions to different pages.

In this emerging line of research, we have developed a prototype system based on SAT-solving techniques to automate the procedure of computing different types of linear layouts of graphs under different user-specific constraints.

The Online System

The system consists of two main components; the client and the server. The client side is built upon an easy-to-use editor and is hosted at the University of Ioannina. The server sides, that are responsible for the actual computations, are hosted at the Universities of Trier and Tübingen.
Access the system Access the code

Documentation

The system supports several standard procedures that a domain expert needs when interacting with such linear layouts (e.g., basic interaction with graphs, additional features to allow the user to define constraints etc). For an overview, refer to the following manuscript at ArXiv.
Read more
 

Contributors

Michael A. Bekos

Michael Kaufmann

Anton Kandlbinder

Julia Maennecke

Maritina Ntasiou

Maria Eleni Pavlidi

Anton Ptassek

Xenia Rieger

George Velissaris

Jessica Wolz

 

Research Output

  1. A. M. Ntasiou, Engineering Barnette's Conjecture with SAT. Master Thesis, Dept. of Mathematics, U. Ioannina, 2025.
  2. G. Velissaris, Linear Layouts With Biarcs. Master Thesis, Dept. of Mathematics, U. Ioannina, 2024.
  3. M. A. Bekos, M. Kaufmann, M. E. Pavlidi, X. Rieger: On the Deque and Rique Numbers of Complete and Complete Bipartite Graphs. CCCG 2023: 89-95, 2023.
  4. M. E. Pavlidi, Linear Graph Layouts of Advanced Data Structures. Master Thesis, Dept. of Mathematics, U. Ioannina, 2023.
  5. X. Rieger, Deque-numbers of Graphs. Bachelor Thesis, Dept. of Computer Science, U. Tübingen, 2023.
  6. P. Angelini, M. A. Bekos, P. Kindermann, T. Mchedlidze: The mixed linear layouts of series-parallel graphs. Theor. Comput. Sci. 936: 129-138, 2022.
  7. A. Kandlbinder, The Local Queue Number from a SAT-Solving Perspective. Bachelor Thesis, Dept. of Computer Science, U. Tübingen, 2021.
  8. M. Jawaherul Alam, M. A. Bekos, V. Dujmovic, M. Gronemann, M. Kaufmann, S. Pupyrev: On dispersable book embeddings. Theor. Comput. Sci. 861: 1-22, 2021.
  9. M. A. Bekos, M. Kaufmann, F. Klute, S. Pupyrev, C. N. Raftopoulou, Torsten Ueckerdt: Four Pages Are Indeed Necessary for Planar Graphs. J. Comput. Geom. 11(1): 332-353, 2020.
  10. J. Md. Alam, M. A. Bekos, M. Gronemann, M. Kaufmann, Sergey Pupyrev: Queue Layouts of Planar 3-Trees. Algorithmica 82(9): 2564-2585, 2020.
  11. J. Männecke, An online tool for interacting with linear layouts. Bachelor Thesis, Dept. of Computer Science, U. Tübingen, 2019.
  12. J. Wolz, Engineering Linear Layouts with SAT. Master Thesis, Universität Tübingen, 2018.
  13. M. A. Bekos, M. Kaufmann, C. Zielke: The Book Embedding Problem from a SAT-Solving Perspective. GD 2015: 125-138, 2015.