Chronological rectangle digraphs which are two-terminal series-parallel

DOI10.1016/J.DAM.2018.05.041MaRDI QIDQ2414469zbMATH OpenOpenAlexWikidataFDO

Authors Jing Huang, Josh Manzer

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

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

Recommendations

• Chronological rectangle digraphs
• Cross-series-parallel digraphs
• Series parallel digraphs with loops
• Chronological orderings of interval digraphs
• Drawing series parallel digraphs symmetrically
• Recognition and characterization of chronological interval digraphs
• How to draw a series-parallel digraph
• Chronological orderings of interval graphs
• HOW TO DRAW A SERIES-PARALLEL DIGRAPH
• Linkless symmetric drawings of series parallel digraphs

Cites work

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

Cited in

(1)

• Chronological rectangle digraphs

This page was built for publication: Chronological rectangle digraphs which are two-terminal series-parallel

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2414469)