Konvexní kresba - Convex drawing

v kreslení grafu, a konvexní kresba a rovinný graf je výkres, který představuje vrcholy grafu jako body v Euklidovské letadlo a hrany jako přímkové segmenty takovým způsobem, že všechny plochy výkresu (včetně vnější plochy) mají konvexní hranici. Hranice obličeje může procházet přímo jedním z vrcholů grafu bez otáčení; A striktně konvexní kresba ptá se navíc, že hranice obličeje se otáčí u každého vrcholu. To znamená, že na striktně konvexní kresbě je každý vrchol grafu také vrcholem každého konvexního polygonu popisujícího tvar každé dopadající plochy.
Každý polyedrický graf má přísně konvexní kresbu,[1] například získaný jako Schlegelův diagram a konvexní mnohostěn představující graf. U těchto grafů lze najít konvexní (ale ne nutně striktně konvexní) kresbu v mřížce, jejíž délka na každé straně je lineární v počtu vrcholů grafu v lineárním čase.[2][3] Striktně konvexní výkresy však mohou vyžadovat větší mřížky; například pro jakýkoli mnohostěn, jako je a pyramida ve kterém jedna plocha má lineární počet vrcholů, striktně konvexní kresba jejího grafu vyžaduje mřížku kubické plochy.[4] Algoritmus lineárního času může najít striktně konvexní kresby polyedrických grafů v mřížce, jejíž délka na každé straně je kvadratická.[5]

Jiné grafy, které nejsou mnohostěnné, mohou mít také konvexní kresby nebo striktně konvexní kresby. Některé grafy, například kompletní bipartitní graf , mít konvexní kresby, ale ne striktně konvexní kresby. Je známa kombinatorická charakterizace grafů s konvexními kresbami,[6] a mohou být rozpoznány v lineárním čase,[7] ale rozměry mřížky potřebné pro jejich výkresy a efektivní algoritmus pro konstrukci malých konvexních mřížkových výkresů těchto grafů nejsou ve všech případech známy.[8]
Konvexní kresby by měly být odlišeny od konvexní vložení, ve kterém musí každý vrchol ležet uvnitř konvexní obal sousedních vrcholů. Konvexní embeddings mohou existovat v jiných rozměrech než dvě, nevyžadují, aby jejich graf byl rovinný, a dokonce i pro rovinné vložení rovinných grafů nemusí nutně nutit konvexní vnější plochu.[9]
Reference
- ^ Tutte, W. T. (1960), "Konvexní reprezentace grafů", Proceedings of the London Mathematical SocietyTřetí série, 10: 304–320, doi:10.1112 / plms / s3-10.1.304, PAN 0114774
- ^ Kant, G. (1996), „Kreslení rovinných grafů pomocí kanonického uspořádání“, Algorithmica, 16 (1): 4–32, doi:10,1007 / s004539900035, hdl:1874/16676, PAN 1394492
- ^ Bonichon, Nicolas; Felsner, Stefan; Mosbah, Mohamed (2007), „Konvexní kresby grafů se 3 spojenými rovinami“, Algorithmica, 47 (4): 399–420, doi:10.1007 / s00453-006-0177-6, PAN 2304987, S2CID 375595
- ^ Andrews, George E. (1963), „Dolní mez pro objem přísně konvexních těles s mnoha hraničními mřížovými body“, Transakce Americké matematické společnosti, 106 (2): 270–279, doi:10.2307/1993769, JSTOR 1993769, PAN 0143105
- ^ Bárány, Imre; Rote, Günter (2006), „Striktně konvexní kresby rovinných grafů“, Documenta Mathematica, 11: 369–391, arXiv:cs / 0507030, PAN 2262937
- ^ Thomassen, Carsten (1980), „Rovinnost a dualita konečných a nekonečných grafů“, Journal of Combinatorial Theory, Řada B, 29 (2): 244–271, doi:10.1016/0095-8956(80)90083-0, PAN 0586436
- ^ Chiba, Norishige; Yamanouchi, Tadashi; Nishizeki, Takao (1984), „Lineární algoritmy pro konvexní kresby rovinných grafů“, Bondy, J. Adrian; Murty, USA (eds.), Pokrok v teorii grafů (Waterloo, Ont., 1982), Academic Press, s. 153–173, PAN 0776799
- ^ Zhou, Xiao; Nishizeki, Takao (2010), „Konvexní kresby grafů s vnitřně propojenými rovinami na mřížky ", Diskrétní matematika, algoritmy a aplikace, 2 (3): 347–362, doi:10.1142 / S179383091000070X, PAN 2728831
- ^ Linial, N.; Lovász, L.; Wigderson, A. (1988), „Gumičky, konvexní vložení a připojení grafů“, Combinatorica, 8 (1): 91–102, doi:10.1007 / BF02122557, PAN 0951998, S2CID 6164458