Reprezentování sériově-paralelních grafů jako průnikových grafů úseček se třemi směry

Abstrakt

V tomto článku ukážeme, že sériově-paralelní grafy (tedy grafy bez minoru K_4) mohou být reprezentovány jako dotykové grafy úseček ve třech směrech. Navíc se v naší reprezentaci neprotínají žádné dvě úsečky ve stejném směru.

Klíčová slova

• Representing
• Series-parallel
• Graphs
• Intersection
• Graphs
• Segments
• Three
• Directions