Rozměr intervalového grafu

V teorii grafů  je intervalová dimenze grafu invariantem grafu , který zavedl Fred S. Roberts v roce 1969.

Intervalová dimenze grafu je minimální dimenze , ve které lze daný graf znázornit jako graf průsečíků hyperobdélníků (tj. vícerozměrných pravoúhlých rovnoběžnostěnů) s hranami rovnoběžnými s osami. To znamená, že musí existovat vzájemná korespondence mezi vrcholy grafu a sadou hyperobdélníků, takže obdélníky se protínají právě tehdy, když existuje hrana spojující odpovídající vrcholy.

Příklady

Obrázek ukazuje graf se šesti vrcholy a znázornění tohoto grafu jako průsečíkový graf (obyčejných dvourozměrných) obdélníků. Tento graf nelze znázornit jako graf průsečíků obdélníků menšího rozměru (v tomto případě segmentů), proto je intervalový rozměr grafu dva.

Roberts [1] ukázal, že 2n - vrcholový graf vytvořený vymazáním dokonalé shody z kompletního 2n-vrcholového grafu má intervalovou dimenzi přesně n  — každý pár nespojených vrcholů musí být reprezentován jako hyperobdélníky, které musí být odděleny jiným způsobem než další dvojice rozměrů. Hyperobdélníkové znázornění tohoto grafu s rozměrem přesně n lze nalézt zesílením každé z 2n ploch n - rozměrné hyperkrychle na hyperobdélník. V důsledku tohoto výsledku se takovým grafům začalo říkat Robertsovy grafy [2] , i když jsou známější jako „party“ grafy a lze je také považovat za Turanovy grafy T (2 n , n ).

Vztah k jiným třídám grafů

Graf má intervalový rozměr nanejvýš jeden tehdy a jen tehdy, když se jedná o intervalový graf . Intervalová dimenze libovolného grafu G  je minimální počet intervalových grafů se stejnou množinou vrcholů (jako G ) tak, že průnik hranových množin intervalových grafů dává G . Jakýkoli vnější rovinný graf má intervalový rozměr nejvýše dva [3] a každý rovinný graf má intervalový rozměr nejvýše tři [4] .

Pokud má bipartitní graf intervalový rozměr dva, lze jej znázornit jako graf průsečíků úseků rovnoběžných s osami v rovině [5] .

Algoritmické výsledky

Mnoho problémů s grafy lze vyřešit nebo aproximovat efektivněji na grafech s omezeným intervalem. Například největší klikový problém lze vyřešit v polynomiálním čase pro grafy s omezeným intervalovým rozměrem [6] . Pro některé další problémy na grafech lze nalézt efektivní řešení nebo aproximaci, pokud je zobrazení ve formě průniku nízkorozměrných hypermogoedrů [7] .

Nalezení takových reprezentací však může být obtížné — kontrola, zda intervalová dimenze daného grafu přesahuje nějakou předem stanovenou hodnotu K , je NP-úplný problém, dokonce i pro K = 2 [8] . Chandran, Francis a Sivadasan [9] popsali algoritmy pro nalezení reprezentací hyperobdélníkových průsečíků libovolných grafů s rozměrem, který je v rámci logaritmického faktoru největší síly grafu . Tento výsledek poskytuje horní hranici intervalového rozměru grafu.

Přes obtížnost přirozených parametrů je intervalová dimenze grafu problém s pevnými parametry řešitelný , pokud se parametrizace provádí podle počtu pokrytí vrcholů vstupního grafu [10] .

Poznámky

  1. ↑ Roberts, 1969 .
  2. ↑ Viz například články od Chandrana, Francise a Sivadasana (2010 ), Chandrana a Sivadasana Chandrana, Sivadasana (2007 ).
  3. ↑ Scheinerman, 1984 .
  4. ↑ Thomassen, 1986 .
  5. ↑ Bellantoni, Hartman, Przytycka, Whitesides, 1993 .
  6. ↑ Chandran, Francis a Sivadasan (2010 ) poznamenali, že to vyplývá ze skutečnosti, že tyto grafy mají polynomiální počet maximálních kliků . Explicitní reprezentace jako průsečík hyperobdélníků nevyžaduje výčet všech maximálních kliků.
  7. ↑ Viz například Agarwal, van Kreveld, Suri (1998 ) a Berman, DasGupta, Muthukrishnan, Ramaswami (2001 ) pro největší aproximace nezávislých množin pro grafy průniků obdélníků a Chlebík, Chlebíková (2005 ) pro diskusi o obtížnosti aproximace těchto problémů pro velké rozměry
  8. ↑ Cozzens (1981 ) ukázal, že výpočet intervalové dimenze grafu je NP-úplný problém. Yannakakis (1982 ) ukázal, že i kontrola, zda rozměr intervalu nepřesahuje 3, je NP-těžký. Konečně Kratochvíl (1994 ) ukázal, že rozpoznání intervalové dimenze = 2 je NP-těžký problém.
  9. ↑ Chandran, Francis, Sivadasan, 2010 .
  10. ↑ Adiga, Chitnis, Saurabh, 2010 .

Literatura