Top

Published in:

2017 | OriginalPaper | Chapter

10. Some Research Topics

Author : Md. Saidur Rahman

Published in: Basic Graph Theory

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this chapter, we introduce some research areas where the students learning graph theory may find interest. Since graphs have applications in modeling many real-world problems, a researcher in graph theory can work on fundamental properties of graphs as well as developing graph models for practical applications and on devising efficient algorithms.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Special Classes of Graphs

Spinrad, J.P.: Efficient Graph Representations. American Mathematical Society, Providence (2003)CrossRefMATH

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall Inc., Upper Saddle River (1999)MATH

Kaufmann, M., Wagner, D. (eds.): Drawing Graphs: Methods and Models. Lecture Notes in Computer Science, vol. 2025. Springer, Berlin (2001)

Sugiyama, K.: Graph Drawing and Applications for Software and Knowledge Engineers. World Scientific, Singapore (2002)

Nishizeki, T., Rahman, M.S.: Planar Graph Drawing. World Scientific, Hackensack (2004)CrossRefMATH

Tamassia, R. (Ed.): Handbook of Graph Drawing and Visualization, CRC Press (2014)

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10, 41–51 (1990)MathSciNetCrossRefMATH

Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of First ACM-SIAM Symposium on Discrete Algorithms, San Francisco, pp. 138–148 (1990)

Chrobak, M., Nakano, S.: Minimum-width grid drawings of plane graphs. Comp. Geom. Theory Appl. 11, 29–54 (1998)MathSciNetCrossRefMATH

10.

Miura, K., Nakano, S., Nishizeki, T.: Grid drawings of 4-connected plane graphs. Discret. Comput. Geom. 26(1), 73–87 (2001)MathSciNetCrossRefMATH

11.

Garg, A., Rusu, A.: Straight-line drawings of binary trees with linear area and arbitrary aspect ration. Proceedings of Graph Drawing 2002. Lecture Notes in Computer Science, vol. 2528, pp. 320–331. Springer, Berlin (2002)

12.

Garg, A., Rusu, A.: A more practical algorithm for drawing binary trees in linear area with arbitrary aspect ratio. In: Proceedings of Graph Drawing 2003, Lecture Notes in Computer Science, vol. 2912, pp. 159–165. Springer (2003)

13.

Brandenburg, F., Eppstein, D., Goodrich, M.T., Kobourov, S., Liotta, G., Mutzel, P.: Selected open problems in graph drawing. In: Proceedings of Graph Drawing 2003, Lecture Notes in Computer Science, vol. 2912, pp. 515–539. Springer (2003)

14.

Garg, A., Rusu, A.: Area-efficient drawings of outerplanar graphs. In: Proceedings of Graph Drawing 2003, Lecture Notes in Computer Science, vol. 2912, pp. 129–134. Springer (2003)

15.

Di Battista, G., Frati, F.: Small area drawings of outerplanar graphs. In: Proceedings of Graph Drawing 2005, Lecture Notes in Computer Science, vol. 3843, pp. 89–100. Springer (2005)

16.

Karim, M.R., Rahman, M.S.: On a class of planar graphs with straight-line grid drawings on linear area. J. Graph Algorithms Appl. 13(2), 153–177 (2009)MathSciNetCrossRefMATH

17.

Tutte, W.T.: Convex representations of graphs. Proc. London Math. Soc. 10, 304–320 (1960)MathSciNetCrossRefMATH

18.

Tutte, W.T.: How to draw a graph. Proc. of London Math. Soc. 13, 743–768 (1963)MathSciNetCrossRefMATH

19.

Chiba, N., Yamanouchi, T., Nishizeki, T.: Linear algorithms for convex drawings of planar graphs. In: Bondy, J.A., Murty, U.S.R. (eds.) Progress in Graph Theory, pp. 153–173. Academic Press, Canada (1984)

20.

Chrobak, M., Kant, G.: Convex grid drawings of 3-connected planar graphs. Inter. J. Comput. Geom. Appl. 7(3), 211–223 (1997)MathSciNetCrossRef

21.

Miura, K., Azuma, M., Nishizeki, T.: Convex drawings of plane graphs of minimum outer apices. Int. J. Found. Comput. Sci. 17, 1115–1127 (2006)MathSciNetCrossRefMATH

22.

Miura, K., Nakano, S., Nishizeki, T.: Convex grid drawings of four connected plane graphs. Int. J. Found. Comput. Sci. 17, 1032–1060 (2006)MathSciNetMATH

23.

Zhou, X., Nishizeki, T.: Convex drawings of internally triconnected plane graphs on \(o(n^2)\) grids. Discret. Math. Algorithms Appl. 2, 347–362 (2010)MathSciNetCrossRefMATH

24.

Lengauer, T.: Combinatorial Algorithms for Integrated Circuit Layout. Wiley, Chichester (1990)MATH

25.

Garg, A., Tamassia, R.: A new minimum cost flow algorithm with applications to graph drawing. In: Proceedings of Graph Drawing ’96, Lecture Notes in Computer Science, vol. 1190, pp. 201–216. Springer (1997)

26.

Rahman, M.S., Nakano, S., Nishizeki, T.: A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs. J. Graph Alg. Appl. 3(4), 31–62 (1999). http://jgaa.info

27.

Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16(3), 421–444 (1987)MathSciNetCrossRefMATH

28.

Rahman, M.S., Nishizeki, T., Naznin, M.: Orthogonal drawings of plane graphs without bends. J. Graph Alg. Appl. 7(4), 335–362 (2003). http://jgaa.info

29.

Thomassen, C.: Plane Representations of Graphs. In: Bondy, J.A., Murty, U.S.R. (eds.) Progress in Graph Theory, pp. 43–69. Academic Press, Canada (1984)

30.

Bhasker, J., Sahni, S.: A linear algorithm to find a rectangular dual of a planar triangulated graph. Algorithmica 3, 247–278 (1988)MathSciNetCrossRefMATH

31.

Kant, G., He, X.: Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theory Comput. Sci. 172, 175–193 (1997)MathSciNetCrossRefMATH

32.

Rahman, M.S., Nakano, S., Nishizeki, T.: Rectangular grid drawings of plane graphs. Comp. Geom. Theory Appl. 10(3), 203–220 (1998)MathSciNetCrossRefMATH

33.

Biedl, T.C.: Optimal orthogonal drawings of triconnected plane graphs. In: Proceedings of SWAT’96, Lecture Notes in Computer Science, vol. 1097, pp. 333–344 (1996)

34.

Biedl, T.C., Kaufmann, M.: Area-efficient static and incremental graph drawings. In: Proceedings of 5th European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 1284, pp. 37–52. Springer (1997)

35.

Papakostas, A., Tollis, I.G.: Efficient orthogonal drawings of high degree graphs. Algorithmica 26, 100–125 (2000)MathSciNetCrossRefMATH

36.

Rahman, M.S., Nakano, S., Nishizeki, T.: Box-rectangular drawings of plane graphs. J. Algorithms 37, 363–398 (2000)MathSciNetCrossRefMATH

37.

He, X.: A simple linear time algorithm for proper box rectangular drawings of plane graphs. J. Algorithms 40(1), 82–101 (2001)MathSciNetCrossRefMATH

38.

Rahman, M.S., Miura, K., Nishizeki, T.: Octagonal drawings of plane graphs with prescribed face areas. Comput. Geom. 42(3), 214–230 (2009)MathSciNetCrossRefMATH

39.

Alam, M.J., Kobourov, S.G., Mondal, D.: Orthogonal layout with optimal face complexity. In: Proceedings of SOFSEM 2016, Lecture Notes in Computer Science, vol. 9587, pp. 121–133 (2016)

40.

Ikebe, Y., Perles, M.A., Tamura, A., Tokunaga, S.: The rooted tree embedding problem into points in the plane. Discret. Comput. Geom. 11, 51–63 (1994)MathSciNetCrossRefMATH

41.

Bose, P.: On embedding an outer-planar graph in a point set. Comput. Geom. Theory Appl. 23(3), 303–312 (2002)MathSciNetCrossRefMATH

42.

Cabello, S.: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. J. Graph Algorithms Appl. 10(2), 353–363 (2006)MathSciNetCrossRefMATH

43.

Garcia, A., Hurtado, F., Huemer, C., Tejel, J., Valtr, P.: On embedding triconnected cubic graphs on point sets. Electron. Notes Discret. Math. 29, 531–538 (2007)CrossRefMATH

44.

Nishat, R.I., Mondal, D., Rahman, M.S.: Point-set embed dings of plane 3-trees. Comput. Geom. Theory Appl. 45(3), 88–98 (2012)CrossRefMATH

45.

Durocher, S., Mondal, D.: On the hardness of point-set embeddability. In: Proceedings of WALCOM 2012, Lecture Notes in Computer Science, vol. 7157, pp. 148–159. Springer (2012)

46.

Cardinal, J., Hoffmann, M., Kusters, V.: On universal point sets for planar graphs. In: Proceedings of Thailand-Japan Joint Conference on Computational Geometry and Graphs, LNCS 8296, 30–41 (2013)MATH

47.

Dujmovic, V., Evans, W.S., Lazard, S., Lenhart, W., Liotta, G., Rappaport, D., Wismath, S.K.: On point-sets that support planar graphs. Comput. Geom. Theory Appl. 46(1), 29–50 (2013)MathSciNetCrossRefMATH

48.

Dujmovic, V., Evans, W.S., Kobourov, S.G., Liotta, G., Weibel, C., Wismath, S.K.: On graphs supported by line sets In: Proceedings of Graph Drawing 2010, LNCS 6502, pp. 177–182 (2011)

49.

Hossain, M.I., Mondal, D., Rahman, M.S., Salma, S.A.: Universal line-sets for drawing planar 3-trees. J. Graph Algorithms Appl. 17(2), 59–79 (2013)MathSciNetCrossRefMATH

50.

Di Giacomo, E., Frati, F., Fulek, R., Grilli, L., Krug, M.: Orthogeodesic point-set embedding of trees. In: Proceedings of Graph Drawing 2011, LNCS 7034, pp. 52–63 (2012)

51.

Bläsius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization, pp. 349–381. CRC press (2014)

52.

Garey, M., Johnson, D.: Crossing number is NP-complete. SIAM J. Algebr. Discret. Methods 4(3), 312–316 (1983)MathSciNetCrossRefMATH

53.

Huang, W., Hong, S.-H., Eades, P.: Using eye tracking to investigate graph layout effects. In: Proceedings of 6th Asia-Pacific Symposium on Visualisation 2007 (APVIS2007), pp. 97–100. IEEE (2007)

54.

Huang, W., Hong, S.-H., Eades, P.: Effects of crossing angles. In: Proceedings of IEEE VGTC Pacific Visualization Symposium 2008 (PacificVis 2008), pp. 41–46. IEEE (2008)

55.

Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theor. Comput. Sci. 412(39), 5156–5166 (2011)MathSciNetCrossRefMATH

56.

Eades, P., Liotta, G.: Right angle crossing graphs and 1-planarity. Discret. Appl. Math.161(7–8), 961–969 (2013)

57.

Argyriou, E.N., Bekos, M.A., Symvonis, A.: The straight-line RAC drawing problem is NP-Hard. J. Graph Algorithms Appl. 16(2), 569–597 (2012)MathSciNetCrossRefMATH

58.

Otten, J., Wijk, J.G.V.: Graph representation in interactive layout design. In: Proceedings of IEEE International Symposium On Circuits and Systems, pp. 914–918 (1978)

59.

Tamassia, R., Tollis, I.G.: A unified approach to visibility representations of planar graphs. Discret. Comput. Geom. 1, 321–341 (1986)MathSciNetCrossRefMATH

60.

Dean, A.M., Evans, W., Gethner, E., Laison, J.D., Safari, M.: Bar \(k\)-visibility graphs. J. Graph Algorithms Appl. 11(1), 45–59 (2007)MathSciNetCrossRefMATH

61.

Sultana, S., Rahman, M.S., Roy, A., Tairin, S.: Bar 1-visibility drawings of 1-planar graphs. In: Proceedings of ICAA 2014, LNCS 8321, pp. 62–76. Springer (2014)

62.

Brandenburg, F.J.: 1-visibility representations of 1-planar graphs. J. Graph Algorithms Appl. 18(3), 421–438 (2014)MathSciNetCrossRefMATH

63.

Gallian, J.A.: A dynamic survey of graph labeling. Electron. J. Comb. DS6 (2015)

64.

Raspaud, A., Schroder, H., Sÿkora, O., Török, L.: Vr\({\acute{{\rm{t}}}}\)o, I.: Antibandwidth and cyclic antibandwidth of meshes and hypercubes. Discret. Math. 309(11), 3541–3552 (2009)CrossRefMATH

65.

Rahaman, M.S., Eshan, T.A., Al Abdullah, S., Rahman, M.S.: Antibandwidth problem for itchy caterpillars. In: Proceeding of ICIEV 2014, IEEE Computer Society, pp. 1–6 (2014). doi:10.1109/ICIEV.2014.6850837

66.

Yixun, L., Jinjiang, Y.: The dual bandwidth problem for graphs. J. Zhengzhou Univ. (Natural Science Edition) 35, 1–5 (2003)MathSciNetMATH

67.

Leung, J.Y.-T., Vornberger, O., Witthoff, J.: On some variants of the bandwidth minimization problem. SIAM J. Comput. 13(3), 650–667 (1984)MathSciNetCrossRefMATH

68.

Hun, Y., Kobourov, S., Veeramon, S.: On maximum differential graph coloring. In: GD’10 Proceedings of the 18th International Conference on Graph Drawing, pp. 274–286 (2010)

69.

Donnelly, S., Isaak, G.: Hamiltonian powers in threshold and arborescent comparability graphs. Discret. Math. 202(1–3), 33–44 (1999)MathSciNetCrossRefMATH

70.

Weili, Y., Ju, Z., Xiaoxu, L.: Dual bandwidth of some special trees. J. Zhengzhou Univ. (Natural Science Edition) 35, 16–19 (2003)MathSciNet

71.

Calamoneri, T., Massini, A., Török, L.: Vr\({\acute{{\rm {t}}}}\)o, I.: Antibandwidth of complete \(k\)-ary trees. Discret. Math. 309(22), 6408–6414 (2009)CrossRefMATH

72.

Miller, Z., Pritikin, D.: On separation number of a graph. Networks 19(6), 651–666 (1989)MathSciNetCrossRefMATH

73.

Bekos, M.A., Kaufmann, M., Kobourov, S., Veeramoni, S.: A note on maximum differential coloring of planar graphs. J. Discret. Algorithms (2014). Published online

74.

Wada, K., Kawaguchi, K.: Efficient algorithms for triconnected graphs and 3-edge-connected graphs. In: Proceedings of the 19th International Workshop on Graph Theoretic Concepts in Computer Science (WG’93), Lecture Notes in Computer Science, vol. 790, pp. 132–143. Springer (1994)

75.

Wada, K., Takaki, A., Kawaguchi, K.: Efficient algorithms for a mixed k-partition problem of graphs without specifying bases. In: Proceedings of the 20th International Workshop on Graph Theoretic Concepts in Computer Science (WG’94), Lecture Notes in Computer Science, vol. 903, pp. 319–330. Springer (1995)

76.

Dyer, M.E., Frieze, A.M.: On the complexity of partitioning graphs into connected subgraphs. Discret. Appl. Math. 10, 139–153 (1985)MathSciNetCrossRefMATH

77.

Györi, E.: On division of connected subgraphs. In: Proceedings of 5th Hungarian Combinational Coll., pp. 485–494 (1978)

78.

Lovász, L.: A homology theory for spanning trees of a graph. Acta Math. Acad. Sci. Hunger 30, 241–251 (1977)MathSciNetCrossRefMATH

79.

Suzuki, H., Takahashi, N., Nishizeki, T., Miyano, H., Ueno, S.: An algorithm for tripartitioning 3-connected graphs. J. Inf. Process. Soc. Jpn. 31(5), 584–592 (1990)

80.

Suzuki, H., Takahashi, N., Nishizeki, T.: A linear algorithm for bipartition of biconnected graphs. Inform. Process. Lett. 33(5), 227–232 (1990)

81.

Jou, L., Suzuki, H., Nishizeki, T.: A linear algorithm for finding a nonseparating ear decomposition of triconnected planar graphs, Technical Report of Information Processing Society of Japan, AL40-3 (1994)

82.

Nakano, S., Rahman, M.S., Nishizeki, T.: A linear time algorithm for four-partitioning four-connected planar graphs. Inform. Process. Lett. 62, 315–322 (1997)MathSciNetCrossRefMATH

83.

Nagai, S., Nakano, S.: A Linear-time algorithm for five-partitioning five-connected internally triangulated plane graphs. IEICE Trans. Fundam. E84-A(9), 2330–2337 (2001)

84.

Karim, M.R., Nahiduzzaman, K.M., Rahman, M.S.: A linear-time algorithm for \(k\)-Partitioning Doughnut Graphs. Infocomp J. Comput. Sci. 8(1), 8–13 (2009)

85.

Awal, T., Rahman, M.S.: A linear algorithm for resource tripartitioning triconnected planar graphs. Infocomp J. Comput. Sci. 9(2), 39–48 (2010)

86.

Awal, T., Rahman, M.S.: A linear algorithm for resource four-partitioning four-connected planar graphs. AKCE Int. J. Graphs Comb. 9(1), 11–20 (2012)MathSciNetMATH

87.

Furht, B. (ed.): Handbook of Social Network Technologies and Applications. Springer, Berlin (2010)

88.

Erciyes, K.: Distributed Graph Algorithms for Computer Networks. Springer, London (2013)CrossRefMATH

89.

Jones, N.C., Pevzner, P.: An Introduction to Bioinformatics Algorithms. The MIT Press (2004)

90.

Tomita, E., Akutsu, T., Matsunaga, T.: Efficient algorithms for finding maximum and maximal cliques: effective tools for bioinformatics. In: Laskovski, A.N. (ed.) Biomedical Engineering, pp. 625–638. Communications and Software, Trends in Electronics (2011)

91.

Bahadur, D.K.C., Akutsu, T., Tomita, E., Seki, T., Fujiyama, A.: Point matching under non-uniform distortions and protein side chain packing based on an efficient maximum clique algorithm. Genome Informatics 13, 143–152 (2002)

92.

Kearney, P.E., Munro, J.I., Phillips, D.: Efficient generation of uniform samples from phylogenetic trees. In: Proceedings of the 3rd International Workshop on Algorithms in Bioinformatics (WABI), LNCS 2812, pp. 177–189. Springer (2003)

93.

Yanhaona, M.N., Bayzid, M.S., Rahman, M.S.: Discovering pairwise compatibility graphs. Discret. Math. Algorithms Appl. 2(4), 607–624 (2010)MathSciNetCrossRefMATH

94.

Yanhaona, M.N., Hossain, K.S.M.T., Rahman, M.S.: Pairwise compatibility graphs. J. Appl. Math. Comput. 30, 479–503 (2009)MathSciNetCrossRefMATH

95.

Calamoneri, T., Petreschi, R., Sinaimeri, B.: On relaxing the constraints in pairwise compatibility graphs. In: Proceedings of the 6th International Workshop on Algorithms and Computation (WALCOM), LNCS 7157, pp. 124–135. Springer (2012)

96.

Calamoneri, T., Frascaria, D., Sinaimeri, B.: All graphs with at most seven vertices are pairwise compatibility graphs. Comput. J. (to appear) (2012). http://arxiv.org/abs/1202.4631

97.

Durocher, S., Mondal, D., Rahman, M.S.: On graphs that are not PCGs, In: Proceedings of the 7th International Workshop on Algorithms and Computation (WALCOM), Lecture Notes in Computer Science, vol. 7748, pp. 310–321. Springer (2013)

98.

Calamoneri, T., Sinaimeri, B.: Pairwise compatibility graphs: a survey. SIAM Rev. 58(3), 445–460 (2016)MathSciNetCrossRefMATH

99.

Kant, G.: Augmenting outerplanar graphs. J. Algorithms 21, 1–25 (1996)MathSciNetCrossRefMATH

100.

Abellanas, M., García, A., Hurtado, F., Tejel, J., Urrutia, J.: Augmenting the connectivity of geometric graphs. Comput. Geom. Theory Appl. 40(3), 220–230 (2008)MathSciNetCrossRefMATH

Title: Some Research Topics
Author: Md. Saidur Rahman
Publisher: Springer International Publishing
Book: Basic Graph Theory
Print ISBN: 978-3-319-49474-6

Electronic ISBN: 978-3-319-49475-3

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-49475-3_10

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner