20.500.12556/DKUM-65332 A charaterization of planar median graphs Karakterizacija ravninskih medianskih grafov Median graphs have many interesting properties. One of them is-in connection with triangle free graphs-the recognition complexity. In general the complexity is not very fast, but if we restrict to the planar case the recognition complexity becomes linear. Despite this fact, there is no characterization of planar median graphs in the literature. Here an additional condition is introduced for the convex expansion procedure that characterizes planar median graphs. Medianski grafi imajo mnogo zanimivih lastnosti. Ena izmed njih je, v povezavi z grafi brez trikotnikov, je časovna zahtevnost za prepoznavanje teh grafov. V splošnem ta zahtevnost ni zelo hitra. Če pa se omejimo na ravninske medianske grafe, je časovna zahtevnost linearna. Kljub temu dejstvu v literaturi ne obstaja karakterizacija ravninskih medianskih grafov. V članku je predstavljen dodaten pogoj h konveksni ekspanziji, ki nam karakterizira ravninske medianske grafe. mathematics graf theory median graphs planar graphs expansion matematika teorija grafov medianski grafi ravninski grafi ekspanzija true true true Angleški jezik Slovenski jezik Neznano 2017-03-31 09:59:18 2017-03-31 10:00:10 2022-07-08 03:07:35 2019-07-11 15:14:50 2006 0 0 str. 41-48 št. 1 Letn. 26 2006 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1234-3099 519.17 7487065 14034009 1234-3099 URN:SI:UM:DK:PES7NZFK Discussiones_Mathematicae_Graph_Theory_2006_Peterin_A_charaterization_of_planar_median_graphs.pdf Discussiones_Mathematicae_Graph_Theory_2006_Peterin_A_charaterization_of_planar_median_graphs.pdf 1 07BD705B95A056051225CBD327B81582 9f6188c4643b07a4a04661f73e5315f99c2549448e8580ed2d55932038a2e48c 0b280c42-7c0e-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=110390 http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1299 1 https://dk.um.si/Dokument.php?lang=slv&id=110389 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0