Special graph representation and visualization of semantic networks

V. V. Borisenko ; A. P. Lakhno ; A. M. Chepovskiy

Fundamentalʹnaâ i prikladnaâ matematika, Tome 16 (2010) no. 8, pp. 27-35.

Résumé

A visibility representation of graphs in which each vertex is mapped to a horizontal segment, was originally proposed in 1980s in the context of the VLSI layout construction problem. In this paper, we present an up-to-date survey on this representation and propose a way of its usage in visualization of semantic networks.

Bibliographie

[1] Kasyanov V. N., Evstigneev V. A., Grafy v programmirovanii: obrabotka, vizualizatsiya i primenenie, BKhV-Peterburg, SPb., 2003, 335–448

[2] Lakhno A. P., Chepovskii A. M., Chernobai V. B., “Vizualizatsiya svyazei vydelennogo mnozhestva ob'ektov semanticheskoi seti”, Prikl. informatika, 2010, no. 6(30), 55–61

[3] Andreae T., “Some results on visibility graphs”, Discrete Appl. Math., 40:1 (1992), 5–17 | DOI | MR | Zbl

[4] Di Battista G., Tamassia R., “Algorithms for plane representations of acyclic digraphs”, Theor. Comput. Sci., 61 (1988), 175–198 | DOI | MR | Zbl

[5] Di Battista G., Tamassia R., Tollis I. G., “Constrained visibility representations of graphs”, Inform. Process. Lett., 41 (1992), 1–7 | DOI | Zbl

[6] Bose P., Dean A. M., Hutchinson J. P., Shermer T. C., “On rectangle visibility graphs”, Symp. on Graph Drawing, GD' 96 (Berkeley, California, USA, September 18–20, 1996), Proceedings, Lect. Notes Comput. Sci., 1190, ed. S. North, Springer, Berlin, 1997, 25–44 | DOI

[7] Botebol M. C., Cobos F. J., Dana J. C., Márquez A., Mateos F., Visibility Drawings of Graphs on Surfaces

[8] Chen C. Y., Hung Y. F., Lu H. I., “Visibility representations of four connected plane graphs with near optimal heights”, 16th Int. Symp., GD 2008 (Heraklion, Crete, Greece, September 21–24, 2008), Revised Papers, Lect. Notes Comput. Sci., 5417, eds. I. G. Tollis, M. Patrignani, Springer, Berlin, 2009, 67–77 | DOI | MR | Zbl

[9] Dean A. M., “A layout algorithm for bar-visibility graphs on the Mobius band”, Graph Drawing. 8th Int. Symp., GD 2000 (Colonial Williamsburg, VA, USA, September 20–23, 2000), Proceedings, Lect. Notes Comput. Sci., 1984, ed. J. Marks, Springer, Berlin, 2001, 350–359 | DOI | Zbl

[10] Dean A. M., Evans W., Gethner E., Laison J. D., Safari M. A., Trotter W. T., “Bar $k$-visibility graphs”, J. Graph Alg. Appl., 11:1 (2007), 45–59 | DOI | MR | Zbl

[11] Dean A. M., Veytsel N., “Unit bar-visibility graphs”, Congr. Numer., 160 (2003), 161–175 | MR | Zbl

[12] Duchet P., Hamidoune Y., Vergnas M. L., Meyniel H., “Representing a planar graph by vertical lines joining different levels”, Discrete Math., 46 (1983), 319–321 | DOI | MR | Zbl

[13] Fan J. H., Lin C. C., Lu H. I., Yen H. C., “Width-optimal visibility representations of plane graphs”, 18th Int. Symp., ISAAC 2007 (Sendai, Japan, December 17–19, 2007), Proceedings, Lect. Notes Comput. Sci., 4835, ed. T. Tokuyama, Springer, Berlin, 2007, 160–171 | DOI | MR | Zbl

[14] He X., Wang J. J., Zhang H., “Compact visibility representation of $4$-connected plane graphs”, Combinatorial Optimization and Applications, 4th Int. Conf., COCOA 2010 (Kailua-Kona, HI, USA, December 18–20, 2010), Proceedings, Part I, Lect. Notes Comput. Sci., 6508, eds. W. Wu, O. Daescu, Springer, Berlin, 2010, 339–353 | DOI | MR | Zbl

[15] Hutchinson J. P., “Arc- and cirle-visibility graphs”, Australas. J. Combin., 25 (2002), 241–262 | MR | Zbl

[16] Jayakumar R., Thulasiraman K., Swamy M. N. S., “An optimal algorithm for maximal planarization of nonplanar graphs”, Proc. IEEE Int. Sympos. on Circuits and Systems, 1986, 1237–1240 | MR

[17] Jayakumar R., Thulasiraman K., Swamy M. N. S., “$O(n^2)$ algorithms for graph planarization”, IEEE Trans. Comp.-Aided Design, 8 (1989), 257–267 | DOI

[18] Kant G., “A more compact visibility representation”, Graph-Theoretic Concepts in Computer Science, 19th Int. Workshop, WG' 93 (Utrecht, the Netherlands, June 16–18, 1993), Proceedings, Lect. Notes Comput. Sci., 790, ed. J. van Leeuwen, Springer, Berlin, 1994, 411–424 | DOI | MR

[19] Kant G., “A more compact visibility representation”, Internat. J. Comput. Geom Appl., 7 (1997), 197–210 | DOI | MR

[20] Kant G., Liotta G., Tamassia R., Tollis I. G., “Area requirement of visibility representations of trees”, Proc. 1993 Canadian Conf. on Comput. Geom., Waterloo, Ontario, 1993, 192–197

[21] Lin C. C., Lu H. I., Sun I. F., “Improved compact visibility representation of planar graph via Schnyder's realizer”, SIAM J. Discrete Math., 18 (2004), 19–29 | DOI | MR | Zbl

[22] Luccio F., Mazzone S., Wong C. K., Visibility Graphs, Prog. Naz. Teoria degli Algoritmi. Report 9, Univ. of Pisa, Pisa, 1983

[23] Luccio F., Mazzone S., Wong C. K., “A note on visibility graphs”, Discrete Math., 64:2–3 (1987), 209–219 | DOI | MR | Zbl

[24] Melnikov L. A., Problem at the sixth Hungarian colloquium on combinatorics, Eger, 1981

[25] Mohar B., Rosenstiehl P., “Tessellation and visibility representations of maps on the torus”, Discrete Comput. Geom., 19 (1998), 249–263 | DOI | MR | Zbl

[26] Nummenmaa J., “Constructing compact rectilinear planar layouts using canonical representation of planar graphs”, Theor. Comput. Sci., 99:2 (1992), 213–230 | DOI | MR | Zbl

[27] Otten R. H. J. M., Wijk J. G., “Graph representations in interative layout design”, Proc. IEEE Internat. Sympos. on Circuits and Systems, New York, 1978, 914–918

[28] Rosenstiehl P., Tarjan R. E., “Rectilinear planar layouts and bipolar orientations of planar graphs”, Discrete Comput. Geom., 1:4 (1986), 343–353 | DOI | MR | Zbl

[29] Streinu I., Whitesides S., “Rectangle visibility graphs: characterization, construction and compaction”, 20th Ann. Symp. on Theor. Aspects of Comp. Sci. (Berlin, Germany, February 27 – March 1, 2003), Proceedings, Lect. Notes Comput. Sci., 2607, eds. H. Alt, M. Habib, Springer, Berlin, 2003, 26–37 | DOI | MR | Zbl

[30] Tamassia R., Tollis I. G., “A unified approach to visibility representations of planar graphs”, Discrete Comput. Geom., 1:4 (1986), 321–341 | DOI | MR | Zbl

[31] Tamassia R., Tollis I. G., “Tessellation representations of planar graphs”, Proc. 27th Allerton Conf. Commun. Control Comput., Univ. of Illinois at Urbana-Champaign, September 1989, 48–57

[32] Tamassia R., Tollis I. G., “Representations of graphs on a cylinder”, SIAM J. Discrete Math., 4:1 (1991), 139–149 | DOI | MR | Zbl

[33] Thomassen C., “Plane representations of graphs”, Progress in Graph Theory, eds. J. A. Bondy, U. S. R. Murty, Academic Press, New York, 1984, 43–69 | MR

[34] Tsiaras V., Tollis I. G., “DAGmaps and $\varepsilon$-visibility representations of DAGs”, 17th Int. Symp., GD 2009 (Chicago, IL, USA, September 22–25, 2009), Revised Papers, Lect. Notes Comput. Sci., 5849, eds. D. Eppstein, E. R. Gansner, Springer, Berlin, 2010, 357–368 | DOI | MR | Zbl

[35] Wang J. J., He X., “Compact visibility representation of plane graphs”, 28th Int. Symp. on Theor. Aspects of Comput. Sci., STACS 2011, Leibniz Int. Proc. in Informatics (LIPIcs), 9, eds. T. Schwentick, C. Dürr, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, 2011, 141–152 | MR | Zbl

[36] Wiglesworth L. W., A study of unit bar-visibility graphs, Dissertation, Univ. of Louisville, 2008, 7–13 | MR

[37] Wismath S. K., “Characterizing bar line-of-sight graphs”, SCG' 85. Proc. 1st Ann. ACM Sympos. Comput. Geom., ACM, New York, 1985, 147–152 | DOI

[38] Zhang H., He X., “Nearly optimal visibility representations on plane graphs”, Automata, Languages and Programming, 33rd Int. Colloq., ICALP 2006 (Venice, Italy, July 10–14, 2006), Proceedings, Part I, Lect. Notes Comput. Sci., 4051, eds. M. Bugliesi, B. Preneel, V. Sassone, I. Wegener, Springer, Berlin, 2006, 407–418 | DOI | MR | Zbl