Obloukový diagram - Arc diagram - Wikipedia
v kreslení grafu, an obloukový diagram je styl kreslení grafu, ve kterém jsou vrcholy grafu umístěny podél čáry v Euklidovské letadlo s hranami nakreslenými jako půlkruhy v jedné ze dvou polorovin ohraničených přímkou nebo jako hladké křivky tvořené sekvencemi půlkruhů. V některých případech jsou úsečky samotné čáry také povoleny jako hrany, pokud spojují pouze vrcholy, které jsou za sebou za sebou.
Použití výrazu "obloukový diagram" pro tento druh výkresů následuje po použití podobného typu diagramu pomocí Wattenberg (2002) k vizualizaci vzorů opakování v řetězcích pomocí oblouků k připojení párů stejných podřetězců. Tento styl kreslení grafů je však mnohem starší než jeho název, jehož počátky sahají až do doby práce Saaty (1964) a Nicholson (1968), kteří ke studiu používali obloukové diagramy křížení čísel grafů. Starší, ale méně často používaný název pro obloukové diagramy je lineární vložení.[1]
Heer, Bostock a Ogievetsky (2010) napište, že obloukové diagramy „nemusí vyjadřovat celkovou strukturu grafu tak efektivně jako dvourozměrné rozložení“, ale že jejich rozložení usnadňuje zobrazení vícerozměrných dat souvisejících s vrcholy grafu.
Rovinné grafy
Tak jako Nicholson (1968) pozorováno, každé vložení grafu do roviny může být deformováno do obloukového diagramu, aniž by se změnil jeho počet křížení. Zejména každý rovinný graf má rovinný obloukový diagram. Toto vložení však možná bude muset pro některé jeho okraje použít více než jeden půlkruh.
Pokud je graf nakreslen bez křížení pomocí obloukového diagramu, ve kterém je každá hrana jeden půlkruh, pak je výkres dvoustránkový vkládání knih, něco, co je možné pouze pro subhamiltonovské grafy, podmnožina rovinných grafů.[2] Například a maximální rovinný graf má takové vložení právě tehdy, pokud obsahuje a Hamiltonovský cyklus. Proto nehamiltonovský maximální rovinný graf, jako je Goldner – Hararyův graf nemůže mít rovinné vložení s jedním půlkruhem na hranu. Testování toho, zda daný graf má tento obloukový diagram bez křížení (nebo ekvivalentně, zda má číslo strany dvě) je NP-kompletní.[3]
Každý rovinný graf má však obloukový diagram, ve kterém je každá hrana nakreslena jako a biarc s maximálně dvěma půlkruhy. Silněji každý Svatý-planární orientovaný graf (rovinný směrovaný acyklický graf s jedním zdrojem a jedním dřezem, oba na vnější straně) má obloukový diagram, ve kterém každá hrana tvoří monotónní křivku, přičemž všechny tyto křivky jsou důsledně orientovány od jednoho konce vrcholové linie k druhému.[4] U neorientovaných rovinných grafů je jedním ze způsobů, jak vytvořit obloukový diagram s maximálně dvěma půlkruhy na hranu, rozdělit graf a přidat další hrany tak, aby výsledný graf měl Hamiltonovský cyklus (a tak, aby každá hrana byla rozdělena nanejvýš jednou), a použít řazení vrcholů v Hamiltonovském cyklu jako řazení podél linie.[5]
Minimalizace přechodů
Protože je NP-úplné otestovat, zda daný graf má obloukový diagram s jedním půlkruhem na hranu a bez křížení, je také NP-tvrdé najít obloukový diagram tohoto typu, který minimalizuje počet křížení. Tento problém minimalizace křížení zůstává NP-tvrdý, pro nerovinné grafy, i když je uspořádání vrcholů podél čáry pevné.[1] V případě pevného uspořádání však lze v polynomiálním čase najít vložení bez křížení (pokud existuje) překládáním problému do 2 - uspokojivost problém, ve kterém proměnné představují umístění každého oblouku a omezení zabraňují tomu, aby se křižující oblouky umístily na stejnou stranu vrcholové linie.[6] Navíc v případě pevného uspořádání může být vložení minimalizující křížení přibližný řešením a maximální řez problém v pomocném grafu, který představuje půlkruhy a jejich potenciální přechody (nebo ekvivalentně aproximací verze MAX2SAT instance 2-uspokojivosti).[7]
Cimikowski & Shope (1996), Cimikowski (2002), a On, Sýkora & Vrt'o (2005) diskutovat o heuristice pro hledání diagramů oblouku s několika přechody.
Orientace ve směru hodinových ručiček
Pro výkresy řízené grafy, společnou konvencí je nakreslit každý oblouk ve směru hodinových ručiček, takže oblouky, které jsou směrovány od dřívějšího k pozdějšímu vrcholu v sekvenci, jsou nakresleny nad linií vrcholu a oblouky směřující od pozdějšího k dřívějšímu vrcholu jsou nakresleny níže linie. Tato konvence orientace ve směru hodinových ručiček byla vyvinuta jako součást jiného stylu kreslení grafu uživatelem Fekete a kol. (2003) a aplikováno na obloukové diagramy pomocí Pretorius & van Wijk (2007).
Jiná použití
Obloukové diagramy byly použity Brandes (1999) vizualizovat stavový diagram a posuvný registr, a tím Djidjev & Vrt'o (2002) ukázat, že číslo křížení každého grafu je alespoň kvadratický šířka řezu.
Poznámky
- ^ A b Masuda a kol. (1990).
- ^ Aplikaci půlkruhů na rozložení okrajů v vkládání knih již provedl Bernhart & Kainen (1979), ale zdá se, že je to kvůli explicitnímu propojení obloukových diagramů s vložením dvoustránkových knih Masuda a kol. (1990).
- ^ Chung, Leighton a Rosenberg (1987).
- ^ Giordano a kol. (2007).
- ^ Bekos a kol. (2013).
- ^ Efrat, Erten a Kobourov (2007).
- ^ Cimikowski & Mumey (2007).
Reference
- Bekos, Michael A .; Kaufmann, Michael; Kobourov, Stephen G .; Symvonis, Antonios (2013), „Smooth orthogonal layouts“, Kresba grafu: 20. mezinárodní sympozium, GD 2012 „Redmond, WA, USA, 19. – 21. Září 2012, revidované vybrané dokumenty, Přednášky v informatice, 7704, Springer, str. 150–161, doi:10.1007/978-3-642-36763-2_14, ISBN 978-3-642-36762-5.
- Bernhart, Frank R .; Kainen, Paul C. (1979), „Kniha tloušťky grafu“, Journal of Combinatorial Theory, Řada B, 27 (3): 320–331, doi:10.1016/0095-8956(79)90021-2.
- Brandes, Ulrik (1999), „Lov na graf B“, Kresba grafu: 7. mezinárodní sympozium, GD'99, Hrad Štiřín, Česká republika 15. – 19. Září 1999, Sborník, Přednášky v informatice, 1731, Springer, str. 410–415, doi:10.1007/3-540-46648-7_42, ISBN 978-3-540-66904-3.
- Chung, Fan R. K.; Leighton, Frank Thompson; Rosenberg, Arnold L. (1987), „Vkládání grafů do knih: Problém s rozložením aplikací do designu VLSI“ (PDF), SIAM Journal o algebraických a diskrétních metodách, 8 (1): 33–58, doi:10.1137/0608002.
- Cimikowski, Robert (2002), „Algorithms for the fixed linearross number problem“, Diskrétní aplikovaná matematika, 122 (1–3): 93–115, doi:10.1016 / S0166-218X (01) 00314-6, PAN 1907825.
- Cimikowski, Robert; Mumey, Brendan (2007), „Aproximace pevného počtu lineárních křížení“, Diskrétní aplikovaná matematika, 155 (17): 2202–2210, doi:10.1016 / j.dam.2007.05.009, PAN 2360650.
- Cimikowski, Robert; Shope, Paul (1996), „Algoritmus neuronové sítě pro problém s rozložením grafu“, Transakce IEEE na neuronových sítích, 7 (2): 341–345, doi:10.1109/72.485670, PMID 18255588.
- Djidjev, Hristo; Vrt'o, Imrich (2002), „Vylepšená dolní mez pro křížení čísel“, Kresba grafu: 9. mezinárodní sympozium, GD 2001, Vídeň, Rakousko, 23. – 26. Září 2001, Revised Papers, Přednášky v informatice, 2265, Springer, str. 96–101, doi:10.1007/3-540-45848-4_8, ISBN 978-3-540-43309-5.
- Efrat, Alon; Erten, Cesim; Kobourov, Stephen G. (2007), „Kreslení kruhového oblouku s pevným umístěním v rovinných grafech“, Journal of Graph Algorithms and Applications, 11 (1): 145–164, doi:10,7155 / jgaa.00140.
- Fekete, Jean-Daniel; Wang, David; Dang, Niem; Aris, Aleks; Plaisant, Catherine (2003), „Překrytí grafových odkazů na stromové mapy“, IEEE Symp. o vizualizaci informací, plakátovém kompendiu, s. 82–83.
- Giordano, Francesco; Liotta, Giuseppe; Mchedlidze, Tamara; Symvonis, Antonios (2007), „Výpočet vzestupné topologické knižní vložky vzestupných planárních digrafů“, Algoritmy a výpočet: 18. mezinárodní sympozium, ISAAC 2007, Sendai, Japonsko, 17. – 19. Prosince 2007, sborník, Přednášky v informatice, 4835, Springer, str. 172–183, doi:10.1007/978-3-540-77120-3_17, ISBN 978-3-540-77118-0.
- On, Hongmei; Sýkora, Ondřej; Vrt'o, Imrich (2005), „Minimalizace heuristiky křížení pro dvoustránkové výkresy“, Elektronické poznámky v diskrétní matematice, 22: 527–534, doi:10.1016 / j.endm.2005.06.088.
- Heer, Jeffrey; Bostock, Michael; Ogievetsky, Vadim (2010), „Prohlídka vizualizační zoo“, Komunikace ACM, 53 (6): 59–67, doi:10.1145/1743546.1743567.
- Masuda, Sumio; Nakajima, Kazuo; Kashiwabara, Toshinobu; Fujisawa, Toshio (1990), „Minimalizace křížení v lineárním vložení grafů“, Transakce IEEE na počítačích, 39 (1): 124–127, doi:10.1109/12.46286, PAN 1032144.
- Nicholson, T. A. J. (1968), „Permutační postup pro minimalizaci počtu křížení v síti“, Sborník institucí elektrotechniků, 115: 21–26, doi:10.1049 / kus.1968.0004, PAN 0311416.
- Pretorius, A. J .; van Wijk, J. J. (2007), „Překlenutí sémantické mezery: Vizualizace přechodových grafů pomocí uživatelem definovaných diagramů“, Počítačová grafika a aplikace IEEE, 27 (5): 58–66, doi:10.1109 / MCG.2007.121, PMID 17913025, S2CID 8643133.
- Saaty, Thomas L. (1964), „Minimální počet křižovatek v celých grafech“, Sborník Národní akademie věd Spojených států amerických, 52 (3): 688–690, doi:10.1073 / pnas.52.3.688, PAN 0166772, PMC 300329, PMID 16591215.
- Wattenberg, M. (2002), „Arc diagrams: visualizing structure in strings“, Proc. Sympozium IEEE o vizualizaci informací (INFOVIS 2002), str. 110–116, doi:10.1109 / INFVIS.2002.1173155, ISBN 0-7695-1751-X, S2CID 881989.