DROPS

Document

Poster Abstract

DOI: 10.4230/LIPIcs.GD.2025.49

Defective Linear Layouts of Graphs (Poster Abstract)

Authors: Michael A. Bekos, Carla Binucci, Emilio Di Giacomo, Walter Didimo, Luca Grilli, Maria Eleni Pavlidi, Alessandra Tappini, and Alexandra Weinberger

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract

A linear layout of a graph defines a total order of the vertices and partitions the edges into either stacks or queues, i.e., crossing-free and non-nested sets of edges along the order, respectively. In this work, we study defective linear layouts that allow forbidden patterns among edges of the same set. Our focus is on k-defective stack layouts and k-defective queue layouts, in which the conflict graph representing the forbidden patterns among the edges of each stack or queue has maximum degree at most k.

Cite as

Michael A. Bekos, Carla Binucci, Emilio Di Giacomo, Walter Didimo, Luca Grilli, Maria Eleni Pavlidi, Alessandra Tappini, and Alexandra Weinberger. Defective Linear Layouts of Graphs (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 49:1-49:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.GD.2025.49,
  author =	{Bekos, Michael A. and Binucci, Carla and Di Giacomo, Emilio and Didimo, Walter and Grilli, Luca and Pavlidi, Maria Eleni and Tappini, Alessandra and Weinberger, Alexandra},
  title =	{{Defective Linear Layouts of Graphs}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{49:1--49:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.49},
  URN =		{urn:nbn:de:0030-drops-250350},
  doi =		{10.4230/LIPIcs.GD.2025.49},
  annote =	{Keywords: Linear layouts, stack layouts, queue layouts, defective layouts}
}

Search Results

Documents authored by Pavlidi, Maria Eleni

Defective Linear Layouts of Graphs (Poster Abstract)

Abstract

Cite as

Thanks for your feedback!

Could not send message