Fault-tolerant distance labeling for planar graphs
Authors: 
Aviv Bar-Natan, Panagiotis Charalampopoulos, Paweł Gawrychowski, 
Shay Mozes, Oren WeimannAuthors Info & Claims
References
[1]
S. Kannan, M. Naor, S. Rudich, Implicit representation of graphs, SIAM J. Discrete Math. 5 (4) (1992) 596–603,.
[2]
S. Alstrup, S. Dahlgaard, M.B.T. Knudsen, Optimal induced universal graphs and adjacency labeling for trees, J. ACM 64 (4) (2017) 27:1–27:22,.
[3]
C. Petersen, N. Rotbart, J.G. Simonsen, C. Wulff-Nilsen, Near-optimal adjacency labeling scheme for power-law graphs, in: 43rd ICALP, 2016, pp. 133:1–133:15,.
[4]
S. Alstrup, H. Kaplan, M. Thorup, U. Zwick, Adjacency labeling schemes and induced-universal graphs, SIAM J. Discrete Math. 33 (1) (2019) 116–137,.
[5]
N. Alon, R. Nenadov, Optimal induced universal graphs for bounded-degree graphs, in: 28th SODA, 2017, pp. 1149–1157,.
[6]
N. Bonichon, C. Gavoille, A. Labourel, Short labels by traversal and jumping, Electron. Notes Discrete Math. 28 (2007) 153–160,.
[7]
M. Katz, N.A. Katz, A. Korman, D. Peleg, Labeling schemes for flow and connectivity, SIAM J. Comput. 34 (1) (2004) 23–40,.
[8]
T. Hsu, H. Lu, An optimal labeling for node connectivity, in: 20th ISAAC, 2009,.
[9]
A. Korman, Labeling schemes for vertex connectivity, ACM Trans. Algorithms 6 (2) (2010) 39:1–39:10,.
[10]
D. Peleg, Informative labeling schemes for graphs, Theor. Comput. Sci. 340 (3) (2005) 577–593,.
[11]
N.G. Rotbart, New ideas on labeling schemes, Ph.D. thesis University of Copenhagen, 2016.
[12]
R.L. Graham, H.O. Pollak, On embedding graphs in squashed cubes, in: Y. Alavi, D.R. Lick, A.T. White (Eds.), Graph Theory and Applications, Springer, Berlin Heidelberg, Berlin, Heidelberg, 1972, pp. 99–110.
[13]
D. Peleg, Proximity-preserving labeling schemes, J. Graph Theory 33 (3) (2000) 167–176.
[14]
C. Gavoille, D. Peleg, S. Pérennes, R. Raz, Distance labeling in graphs, J. Algorithms 53 (1) (2004) 85–112,.
[15]
P. Gawrychowski, P. Uznański, Better distance labeling for unweighted planar graphs, in: 17th WADS, 2021, pp. 428–441,.
[16]
C. Gavoille, M. Katz, N.A. Katz, C. Paul, D. Peleg, Approximate distance labeling schemes, in: 9th ESA, 2001, pp. 476–487,.
[17]
A. Gupta, A. Kumar, R. Rastogi, Traveling with a pez dispenser (or, routing issues in MPLS), in: 42nd FOCS, 2001, pp. 148–157,.
[18]
M. Thorup, Compact oracles for reachability and approximate distances in planar digraphs, J. ACM 51 (6) (2004) 993–1024,.
[19]
I. Abraham, C. Gavoille, Object location using path separators, in: 25th PODC, ACM, 2006, pp. 188–197,.
[20]
J. Feigenbaum, D.R. Karger, V.S. Mirrokni, R. Sami, Subjective-cost policy routing, in: 1st WINE, 2005, pp. 174–183,.
[21]
J. Feigenbaum, D.R. Karger, V.S. Mirrokni, R. Sami, Subjective-cost policy routing, Theor. Comput. Sci. 378 (2) (2007) 175–189,.
[22]
A.D. Twigg, Compact forbidden-set routing, Tech. Rep. UCAM-CL-TR-678 University of Cambridge, Computer Laboratory, Dec. 2006, https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-678.pdf.
[23]
B. Courcelle, C. Gavoille, M.M. Kanté, Compact labelings for efficient first-order model-checking, J. Comb. Optim. 21 (1) (2009) 19–46,.
[24]
B. Courcelle, A. Twigg, Constrained-path labellings on graphs of bounded clique-width, Theory Comput. Syst. 47 (2) (2010) 531–567,.
[25]
I. Abraham, S. Chechik, C. Gavoille, D. Peleg, Forbidden-set distance labels for graphs of bounded doubling dimension, ACM Trans. Algorithms 12 (2) (2016) 22:1–22:17,.
[26]
I. Abraham, S. Chechik, C. Gavoille, Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels, in: 44th STOC, 2012, pp. 1199–1218,.
[27]
Y. Emek, D. Peleg, L. Roditty, A near-linear-time algorithm for computing replacement paths in planar directed graphs, ACM Trans. Algorithms 6 (4) (2010) 64:1–64:13,.
[28]
P.N. Klein, S. Mozes, O. Weimann, Shortest paths in directed planar graphs with negative lengths: a linear-space O ( n log 2 n )-time algorithm, ACM Trans. Algorithms 6 (2) (2010) 30:1–30:18,.
[29]
C. Wulff-Nilsen, Solving the replacement paths problem for planar directed graphs in O ( n log n ) time, in: 21st SODA, 2010, pp. 756–765,.
[30]
S. Baswana, U. Lath, A.S. Mehta, Single source distance oracle for planar digraphs avoiding a failed node or link, in: 23rd SODA, 2012, pp. 223–232,.
[31]
P. Charalampopoulos, S. Mozes, B. Tebeka, Exact distance oracles for planar graphs with failing vertices, ACM Trans. Algorithms (2022),.
[32]
G.F. Italiano, A. Karczmarz, N. Parotsidis, Planar reachability under single vertex or edge failures, in: 32nd SODA, 2021, pp. 2739–2758,.
[33]
J. Fakcharoenphol, S. Rao, Planar graphs, negative weight edges, shortest paths, and near linear time, J. Comput. Syst. Sci. 72 (5) (2006) 868–889,.
[34]
P.N. Klein, Multiple-source shortest paths in planar graphs, in: 16th SODA, 2005, pp. 146–155. http://dl.acm.org/citation.cfm?id=1070432.1070454.
[35]
G.F. Italiano, Y. Nussbaum, P. Sankowski, C. Wulff-Nilsen, Improved algorithms for min cut and max flow in undirected planar graphs, in: 43rd STOC, 2011, pp. 313–322,.
[36]
H. Kaplan, S. Mozes, Y. Nussbaum, M. Sharir, Submatrix maximum queries in monge matrices and partial monge matrices, and their applications, ACM Trans. Algorithms 13 (2) (2017) 26:1–26:42,.
[37]
I. Bezáková, A. Searns, On counting oracles for path problems, in: 29th ISAAC, 2018, pp. 56:1–56:12,.
[38]
S. Mozes, C. Wulff-Nilsen, Shortest paths in planar graphs with real lengths in O ( n log 2 n / log log n ) time, in: 18th ESA, 2010, pp. 206–217,.
[39]
G.L. Miller, Finding small simple cycle separators for 2-connected planar graphs, in: 16th STOC, 1984, pp. 376–382,.
[40]
P.N. Klein, S. Mozes, C. Sommer, Structured recursive separator decompositions for planar graphs in linear time, in: 45th STOC, 2013, pp. 505–514,.
[41]
G.N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM J. Comput. 16 (6) (1987) 1004–1022,.
[42]
S. Cabello, E.W. Chambers, J. Erickson, Multiple-source shortest paths in embedded graphs, SIAM J. Comput. 42 (4) (2013) 1542–1571,.
[43]
G. Monge, Mémoire sur la théorie des déblais et des remblais, De l'Imprimerie Royale, 1781.
[44]
P. Gawrychowski, S. Mozes, O. Weimann, C. Wulff-Nilsen, Better tradeoffs for exact distance oracles in planar graphs, in: 29th SODA, 2018, pp. 515–529,.
[45]
P. Charalampopoulos, P. Gawrychowski, S. Mozes, O. Weimann, Almost optimal distance oracles for planar graphs, in: 51st STOC, 2019, pp. 138–151,.
[46]
M. Henzinger, S. Krinninger, D. Nanongkai, T. Saranurak, Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture, in: 47th STOC, 2015, pp. 21–30,.
[47]
A. Abboud, S. Dahlgaard, Popular conjectures as a barrier for dynamic planar graph algorithms, in: 57th FOCS, 2016, pp. 477–486,.
Index Terms
- Fault-tolerant distance labeling for planar graphs
Index terms have been assigned to the content through auto-classification.
Recommendations
Fault-Tolerant Distance Labeling for Planar Graphs
Structural Information and Communication ComplexityAbstractIn fault-tolerant distance labeling we wish to assign short labels to the vertices of a graph G such that from the labels of any three vertices u, v, f we can infer the u-to-v distance in the graph . We show that any directed weighted planar ...
Total domination in planar graphs of diameter two
MacGillivary and Seyffarth [G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory 22 (1996) 213-229] proved that planar graphs of diameter two have domination number at most three. Goddard and Henning [W. Goddard, M.A. ...
Adapted list coloring of planar graphs
Given an edge coloring F of a graph G, a vertex coloring of G is adapted to F if no color appears at the same time on an edge and on its two endpoints. If for some integer k, a graph G is such that given any list assignment L to the vertices of G, with |...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Elsevier B.V.
Publisher
Elsevier Science Publishers Ltd.
United Kingdom
Publication History
Published: 29 May 2022
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 29 Jan 2025