Chronological rectangle digraphs which are two-terminal series-parallel

DOI10.1016/j.dam.2018.05.041zbMath1410.05078OpenAlexW2808957893MaRDI QIDQ2414469

Josh Manzer, Jing Huang

Publication date: 17 May 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.05.041

zbMATH Keywords

chronological rectangle digraphpolynomial-time recognition algorithmtwo-terminal series-parallel digraphforbidden induced subdigraph characterization

Mathematics Subject Classification ID

Graph polynomials (05C31) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chronological rectangle digraphs
• Recognition and characterization of chronological interval digraphs
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Chordal bipartite graphs with high boxicity
• Boxicity of circular arc graphs
• An optimal greedy heuristic to color interval graphs
• Boxicity and cubicity of asteroidal triple free graphs
• Boxicity of graphs with bounded degree
• Interval representations of planar graphs
• A unified approach to domination problems on interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A special planar satisfiability problem and a consequence of its NP- completeness
• Boxicity of graphs on surfaces
• Topology of series-parallel networks
• Incidence matrices and interval graphs
• Boxicity and maximum degree
• Incidence matrices, interval graphs and seriation in archeology
• Boxicity and treewidth
• The LBFS Structure and Recognition of Interval Graphs
• Representation of a finite graph by a set of intervals on the real line
• The Complexity of the Partial Order Dimension Problem
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• The Recognition of Series Parallel Digraphs
• A Characterization of Comparability Graphs and of Interval Graphs
• A unified approach to approximating resource allocation and scheduling
• Boxicity and Poset Dimension