Optimal Linear Arrangement of Interval Graphs

DOI10.1007/11821069_24zbMath1132.68501OpenAlexW1502167149MaRDI QIDQ5756716

Pinar Heggernes, Gregory Kucherov, Dieter Kratsch, Fedor V. Fomin, Johanne Cohen

Publication date: 5 September 2007

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11821069_24

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (16)

Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges ⋮ Minimum Linear Arrangement of Series-Parallel Graphs ⋮ Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs ⋮ Minimum Linear Arrangement of the Cartesian Product of Optimal Order Graph and Path ⋮ Maximum cut on interval graphs of interval count four is NP-complete ⋮ Mixed Search Number and Linear-Width of Interval and Split Graphs ⋮ Complexity of maximum cut on interval graphs ⋮ Lower and upper bounds for the linear arrangement problem on interval graphs ⋮ A note on minimum linear arrangement for BC graphs ⋮ Treewidth and minimum fill-in on permutation graphs in linear time ⋮ Mixed search number and linear-width of interval and split graphs ⋮ A Lex-BFS-based recognition algorithm for Robinsonian matrices ⋮ Linear time algorithms to solve the linear ordering problem for oriented tree based graphs ⋮ Malod and the Pascaline ⋮ The distance orientation problem ⋮ On an ordering problem in weighted hypergraphs

This page was built for publication: Optimal Linear Arrangement of Interval Graphs