Hristo Nikolov Djidjev
Research Interests

Combinatorial algorithms:
shortest paths, graph partitioning, combinatorial optimization

Network analysis: data mining, community structure detection, network visualization

Sensor networks: coverage, placement, optimization

Algorithm engineering: efficient implementation of combinatorial algorithms
Professional Experience
Technical staff member, Los Alamos National Lab, Los Alamos, 2005current
Research Adjunct Professor, Carleton University, Ottawa, 1990current
Senior Lecturer, University of Warwick, 19982002
Assistant Professor and Research Scientist, Rice University,
19921998
Visiting Professor, Duke University, 1990
Visiting Professor, MIT, 1989
Research Associate and Senior Research Associate,
Center of Informatics and Computer Technology,
Bulgarian Academy of Sciences, 19851991
Education
Ph. D. in Computer Science, Sofia University
M. Sc. in Mathematics, Sofia University
Professional Activities
Editorial Service:
 Member of the standing committee and editor of Parallel
Processing Letters
 Editor of Discrete Mathematics and Theoretical Computer Science
 Chairman of the organizing committee of the international workshop on
Optimal Algorithms
 Editor of vol. 401 of Lecture Notes of Computer Science
 Reviewer for Algorithmica, Computational
Geometry: Theory and Applications, Journal of Algorithms,
Information and Computation, Information Processing
Letters, Networks, SIAM Journal on Computing, SIAM Journal of Discrete
Mathematics, Theoretical Computer Science, National Science
Foundation, and others
University and Departmental Service:
 Member of the Library Committee
 Member of the Environmental Strategic Planning Committee
 Chairman of the Teaching Issues Committee
 Chairman of the Colloquium Committee
 Member of the Undergraduate Committee
 Chairman of Automata or Algorithms qualifying exams
 Speaker at Corporate Affiliates Meetings
 Coordinator for the Workshop on Algorithmic Research in the Midsouthwest
Awards
 EPSRC Award GR/M60750: Algorithms and tools for graph
partitioning, 19992002.
 Future and Emerging Technologies programme of the EU
(ALCOMFT) contract number IST199914186 (as a member of the Warwick
team), 20002003.
 RTDF Award 98/990140 Algorithms and tools for web searching, with
M. Joy and M. Luck, 19992000.
 EPA Award R825207010: Partitioning algorithms and their
application to massively parallel computations of multiphase fluid
flows in porous media, with R. Ewing, R. Lazarov, and M. Vardi,
19962000.
 NSF Award CCR9409181 RIA: Efficient algorithms for special
classes of graphs, 19941997.
Publications
Refereed Journal and Conference Papers

H. Djidjev, A linear algorithm for finding a maximal planar subgraph,
SIAM Journal of Discrete Mathematics, 2006
(to appear).

Hristo Djidjev, Efficient computation of minimum exposure paths in a sensor network field,
Proc. IEEE International Conference on Distributed Computing in Sensor Networks (DCOSS),
in Lecture Notes in Computer Science vol. 4549, LAUR070591,
2007.

Hristo Djidjev, Imrich Vrto, Crossing Numbers and Cutwidths,
J. Graph Algorithms and Applications, vol. 7, no. 3, pp.
245251, 2003.

Lyudmil Aleksandrov, Hristo Djidjev, Hua Guo and Anil Maheshwari,
Partitioning Planar Graphs with Costs and Weights, Proc. of
2nd Workshop on Algorithm Engineering and Experiments
(ALENEX'02), San Francisco, 2002.

H. Djidjev, I. Vrto, An Improved Lower Bound for Crossing
Numbers, Proc. 9th Intl. Symp. on Graph Drawing, Lecture
Notes in Computer Science 2265, Springer Verlag, Berlin, 2002,
pp. 96101.

H. Djidjev, M. Joy, A. Twigg, Collecting and Classifying
Information from the WWW, Proceedings of SSGRR'01
(invited), Rome, 2001.

H. Djidjev, Finding shortest cycles in networks of bounded genus,
International Workshop on Interconnection Networks (IWIN'01),
Vall de Nuria, 2001.

H. Djidjev, Forcedirected methods for smoothing unstructured
triangular and tetrahedral meshes, Proceedings of the 9th
International Meshing Roundtable, October 25, 2000,
New Orleans, pp. 395406.

H. Djidjev, Computing the girth of a planar graph,
International Colloquium on Automata,
Languages and Programming (ICALP'00),
Lecture Notes in Computer Science,
vol. 1853, 2000, pp. 821831.

H. Djidjev, Partitioning planar graphs with vertex costs:
algorithms and applications,
Algorithmica, vol. 28 (2000), pp. 5175.

L. Aleksandrov and H. Djidjev, A Dynamic Algorithm for
Maintaining Graph Partitions, Scandinavian Workshop on Algorithm
Theory (SWAT'00), Lecture Notes in Computer Science, vol.
1851, 2000, pp. 7182.

H. Djidjev, Forcedirected methods for mesh improvement, Proc. of
2nd Workshop on Algorithm Engineering and Experiments (ALENEX 00),
2000, pp. 2942.
 H. Djidjev, G. Pantziou and C. Zaroliagis, Improved Algorithms
for Dynamic Shortest Paths, Algorithmica, vol. 28:4, 2000,
pp. 367389.
 L. Alexandrov, H. N. Djidjev, J.R. Sack, Finding a
shortest central link segment of a simple polygon in O(n log
n) time, International Journal of Computational Geometry
and Applications, vol. 10, No. 2, 2000, pp. 157188.
 H. N. Djidjev, J.R. Gilbert, Separators in
graphs with negative or multiple vertex weights, Algorithmica,
vol. 23 (1999), pp. 5771.

L.G. Aleksandrov, H.N. Djidjev, Maintaining Partitions of
Dynamic Planar Meshes, Proceedings of the Canadian Conference on
Computational Geometry (CCCG'98), 1998, pp. 8485.
 H. N. Djidjev, S. M. Venkatesan, Reduced constants
for simple cycle graph separation, Acta Informatica, vol. 34
(1998), pp. 231243.
 H. N. Djidjev, Weighted graph separators and their application,
European Symposium on Algorithms (ESA'97), Lecture Notes in
Computer Science, 1997, vol. 1284, pp. 130143.
 H. N. Djidjev, Efficient Algorithms for
Shortest Path Queries in Planar Digraphs, in Proc. 22nd Workshop on
GraphTheoretic Concepts in Computer Science (WG '96), Lecture
Notes in Computer Science, SpringerVerlag, 1996, pp. 151165.

L. Aleksandrov and H. Djidjev.
Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus.
SIAM Journal of Discrete Mathematics, vol. 9 (1996), pp. 129150.
 H. Djidjev, A Linear Algorithm for the Maximal
Planar Subgraph Problem, in Proceedings of WADS'95, Lecture Notes
in Computer Science, vol. 955, pp. 369380, SpringerVerlag, 1995.
 H. Djidjev, G. Pantziou and C. Zaroliagis, Fast
Algorithms for Maintaining Shortest Paths in Outerplanar and Planar
Digraphs, Proc. 10th Conf. on Fundamentals of Computation Theory
(FCT'95), Lecture Notes in Computer Science, vol. 965,
pp.191200, SpringerVerlag, 1995.
 H. N. Djidjev, S. M. Venkatesan, Planarization of
graphs embedded on surfaces, in Proc. 21st Workshop on GraphTheoretic
Concepts in Computer Science (WG '95), Lecture Notes
in Computer Science, vol. 1017, pp. 6272, SpringerVerlag, 1995.
 H. Djidjev, G. Pantziou, and C. Zaroliagis,
Online and dynamic algorithms for shortest path problems, in
Proc. 12th Symposium on Theoretical Aspects of Computer Science
(STACS'95), LNCS 900, pp.193204, SpringerVerlag, 1995.
 H. N. Djidjev, A. Lingas, On computing
Voronoi diagrams for sorted point sets, International Journal of
Computational Geometry, vol. 5 (1995), pp. 327337.
 H. N. Djidjev, On drawing a graph convexly in the
plane, Graph Drawing '94, DIMACS International Workshop, in
Lecture Notes in Computer Science, vol. 894, SpringerVerlag, 1995,
pp. 7683.
 H. N. Djidjev, K. Diks, O. Sykora, I. Vrto, Edge
separators for planar graphs and their applications, Journal of
Algorithms, vol. 14 (1993), pp. 258279.
 P. Vassilevsky, H. N. Djidjev, Incomplete
block preconditioners for solving elliptic differential equations on
systolic processors, International Journal of Computer
Mathematics, vol. 44 (1992), 341.
 H. N. Djidjev, A. Lingas, and J.R. Sack, An O(n log
n)
algorithm for computing the link center of a simple polygon,
Discrete and Computational Geometry, vol. 8 (1992), pp. 131152.
 H.N. Djidjev, J. Reif, An efficient algorithm for the
genus problem with explicit construction of forbidden subgraphs,
Proc. Annual ACM Symposium on Theory of Computing (STOC) (1991), pp.337347.
 H. Djidjev, A. Lingas, On computing the
Voronoi diagram for restricted planar figures, WADS'91, in
Lecture Notes in Computer Science, SpringerVerlag, Berlin,
Heidelberg, New York, Tokyo (1991), pp. 5464.
 H. Djidjev, O. Garido, C. Levcopoulos, and A. Lingas, On the
maximum qdependent set problem, International Conference for
Young Computer Scientists ICYCS'91, pp. 271274.
 H.N. Djidjev, G.E. Pantziou, C.D. Zaroliagis,
Computing shortest paths and distances in planar graphs, ICALP'91, in
Lecture Notes in Computer Science, SpringerVerlag, Berlin,
Heidelberg, New York, Tokyo (1991), v.510, 327338.
 L. Aleksandrov, H. N. Djidjev, Improved upper and
lower bounds on separation of toroidal graphs, Proc. Optimal
algorithms'89, in Lecture Notes in Computer Science,
SpringerVerlag, Berlin, Heidelberg, New York, Tokyo (1989), vol.401,
126138.
 H. Djidjev, A. Lingas, and J.R. Sack, An O(n log
n)
algorithm for computing a link center in a simple polygon, Proc.
STACS '89, in Lecture Notes in Computer Science,
SpringerVerlag, Berlin, Heidelberg, New York, Tokyo (1989), vol. 349,
96107.
 H. N. Djidjev, Design and analysis of systolic
implementations, J. of New Generation Computing Systems, vol. 1
(1988), 1, 720.
 H. N. Djidjev, Linear algorithms for graph separation
problems,
SWAT'88, Lecture Notes in Computer Science, vol. 318,
SpringerVerlag, Berlin, Heidelberg, New York, Tokyo, 216221 (1988).
 K. Diks, H. N. Djidjev, O. Sykora, I. Vrto, Edge separators for
planar graphs and their applications, MFCS'88, Lecture Notes in
Computer Science, vol. 324, SpringerVerlag, Berlin, Heidelberg, New
York, Tokyo, 280290 (1988).
 L. Aleksandrov, H. N. Djidjev, Solving symmetric
positive definite systems of linear equations on a systolic processor,
Proc. IFIP Working Conference on Parallel Processing, in Parallel
Processing, M. Cosnard, M.H.Barton and M. Vaneschi (Eds.), Elsevier
Science Publishers (North Holland) (1988).
Books and Book Chapters

A. Maheshwari, J.R. Sack, and H. Djidjev, Link Distance Problems,
Chapter in Handbook on Computational Geometry, Elsevier, 2000,
pp. 519558.
 V. Aleksandrov, R. Andonov, H. N. Djidjev, V. Josifov,
and C.Ostromski, Mathematical Aspects of VLSI Design, Sofia,
1989 (in Bulgarian).
Invited talks
Princeton University, CarnegieMellon University, Massachusetts Institute of Technology (MIT), UT Austin, UC Berkeley, Palo Alto Research Center (PARC), University of Washington, University of Lund, MaxPlanck Institute (MPII), King's College London, and others
Personal
hristo@dcs.warwick.ac.uk