Linear Structure of Graphs and the Knotting Graph

Ekkehard Köhler ()
Additional contact information
Ekkehard Köhler: Brandenburgische Technische Universität, Mathematisches Institut

A chapter in Gems of Combinatorial Optimization and Graph Algorithms, 2015, pp 13-27 from Springer

Abstract: Abstract Many important graph classes, such as interval graphs, comparability graphs and AT-free graphs, show some kind of linear structure. In this paper we try to capture the notion of linearity and show some algorithmic implications. In the first section we discuss the notion of linearity of graphs and give some motivation for its usefulness for particular graph classes. The second section deals with the knotting graph, a combinatorial structure that was defined by Gallai long ago and that has various nice properties with respect to our notion of linearity. Next we define intervals of graphs in Sect. 3. This concept generalizes betweenness in graphs—a crucial notion for capturing linear structure in graphs. In the last section we give a practical example of how to use the linear structure of graphs algorithmically. In particular we show how to use these structural insights for finding maximum independent sets in AT-free graphs in $$O(n\overline{m})$$ O ( n m ¯ ) time, where $$\overline{m}$$ m ¯ denotes the number of non-edges of the graph G.

Keywords: Partial Order; Linear Structure; Interval Graph; Comparability Graph; Graph Class (search for similar items in EconPapers)
Date: 2015
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-319-24971-1_2

Ordering information: This item can be ordered from
http://www.springer.com/9783319249711

DOI: 10.1007/978-3-319-24971-1_2

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().