**Farhad Shahrokhi ** Aug. 2000

Department of Computer Science

University of North Texas

Denton Texas, 76205

phone: (office) 940-565-2805 (home)940-382-0098

e-mail: farhad@cs.unt.edu

**Education**

1987 Ph.D. in Mathematics with concentration on graph algorithms,
Western Michigan University

Thesis: The Maximum Concurrent Flow Problem

Thesis Advisor, D.W. Matula

1985-87 Post Doc. and Visiting Scholar, Department of
Computer Science, Southern Methodist University,
hosted by D. W. Matula

1983 M.S. in Computer Science, Western Michigan University

1981 M.S. in Operations Research, Western Michigan University

1976 B.S. in Electrical Engineering, Aryamehr University of Technology,
Tehran, Iran

**Areas of Expertise**

Theoretical Computer Science, Combinatorial Optimization,
Geometric Graph Theory and Combinatorics, Design and Analysis of Algorithms,
Graph Drawing

**Employment History**

2000- Professor (with tenure),
Department of Computer Science, University of North Texas

1994-2000 Associate Professor (with tenure),
Department of Computer Science, University of North Texas

1989-94 Assistant Professor, Department of Computer Science,
University of North Texas

1987-89 Assistant Professor, Department of Computer Science,
New Mexico Tech.

**Research Positions**

1998-1999 (8 weeks) Visiting Scientist, *Center for Discrete Mathematics and Theoretical Computer Science*
(DIMACS), Rutgers University

1988 (6 weeks) Visiting Scientist, *Institute for Mathematics
and its application*, (IMA) University of Minnesota, 1988

**RESEARCH**

All conference and journal papers listed below are refereed. Some of the conference papers are the preliminary version of the journal papers.

**Publications in Refereed Journals**

- 1.
- Shahrokhi, F., Sýkora, O., Székely, L.A., and Vrto, I.,
On bipartite drawings and linear arrangement problem.
To appear in
*SIAM Journal on Computing*. This work is supported by NSF grant CCR 9528228. - 2.
- Shahrokhi, F., Sýkora, O., Székely, L.A., and Vrto, I.,
A New Lower Bound for Bipartite Crossing Number with Algorithmic Applications,
*Theoretical Computer Science*, 245, 2, (2000), 281-294. This work is supported by NSF grant CCR 9528228. - 3.
Shahrokhi, F., Székely, L.A., Constructing integral uniform flows in networks with applications to the edge-forwarding index problem.

*Discrete Applied Math.*107, 3 (2000), 193-209, (in press). This work is supported by NSF grant CCR 9528228.- 4.
- Shahrokhi, F., Shi, W., On Crossing Sets, Disjoint Sets and Pagenumber,
*Journal of Algorithms*, 34, 1 (2000), 40-53. This work is supported by NSF grant CCR 9528228. - 5.
- Shahrokhi, F., Sýkora, O., Székely, L.A., and Vrto, I.,
Intersection of Curves and Crossing Number of
on a Surface,
*Disc. Comp. Geometry*, 19 (1998), 237-247. This work is supported by NSF grant CCR 9528228. - 6.
- Shahrokhi, F. and Székely, L.A.,
Integral Multicommodity Flows in Product Graphs,
*Congressus Numerantium*, 122 (1996), 67-89. - 7.
- Shahrokhi, F., Sýkora, O., Székely, L.A., and Vrto, I.,
The Book Crossing Number of Graphs,
*Journal of Graph Theory*, 21, 4 (1996), 413-424. - 8.
- Shahrokhi, F., Sýkora, O., Székely, L.A., and Vrto, I.,
Bounds for the Crossing Number of a Graph on a Compact Two Manifold,
*Advances in Mathematics*, 123, 2 (1996), 105-119. - 9.
- Shahrokhi, F., Sýkora, O., Székely, L.A., and Vrto, I.,
Drawing of Graphs With a Few Crossings on the Surfaces,
*Special Issue of Algorithmica on Graph Drawing*, 16 (1996), 118-131. - 10.
- Pach, J., Shahrokhi, F. and Szegedy, M., Applications of Crossing Number,
*Special Issue of Algorithmica on Graph Drawing*, 16 (1996), 111-117. - 11.
- Shahrokhi, F. and Székely, L.A.,
On Canonical Concurrent Flows, Crossing Number, and Graph Expansion,
*Combinatorics, Probability and Computing*3 (1994), 1-21. - 12.
- Shahrokhi, F., and Székely. L.A.,
On the Complexity of Bottleneck Bipartite Problem,
*Journal of Combinatorial Mathematics and Combinatorial Computing*, 15 (1994), 221-226. - 13.
- Shahrokhi, F. and Székely, L.A.,
Integral Multicommodity Flow and Packet Routing,
*Congressus Numerantium*, 97 (1993), 2-16. - 14.
- Clark, L., Shahrokhi, F. and Székely, L.A.,
A Linear Time Algorithm for Graph Partition Problems,
*Information Processing Letters*, 42 (1992),19-24. - 15.
- Shahrokhi, F. and Matula, D. W.,
The Maximum Concurrent Flow Problem,
*Journal of Association for Computing Machinery*, 37 (1990), 318-334. - 16.
- Matula, D. W. and Shahrokhi, F.,
Sparsest Cuts and Bottlenecks in Graphs,
*Journal of Disc. Applied Math.*, 27 (1990), 113-123. - 17.
- Shahrokhi, F.,
Approximation Algorithms for the Maximum Concurrent Flow Problem,
*ORSA Journal on Computing*, 1:2 (1989), 62-69. - 18.
- Lindhorst, G. and Shahrokhi, F.,
On Renaming a Set of Clauses as a Horn Set,
*Information Processing Letters*, 30 (1989) 298-303.**Publications in Refereed Conferences**

- 19.
- Shahrokhi, F., Vrto, I.,
On 3-layer drawings and pseudo-arrangements,
in
*Proc. of Graph Drawing 99, (GD99), LNCS*, Springer Verlag, 1999, 225-231. This work is supported by NSF grant CCR 9528228. - 20.
- Shahrokhi, F. and Székely, L.A.,
Integral uniform flows in symmetric networks,
*Proc. of International Workshop on Graph-Theoretic Concepts in Computer Science, WG1998, LNCS*, Springer Verlag, 1998, 272-284. This work is supported by NSF grant CCR 9528228. - 21.
- Shahrokhi, F., Székely, L.A., Vrto, I.,
Bipartite crossing numbers of meshes and cubes,
*Proc. of Graph Drawing 97, (GD97), LNCS*1353, Springer Verlag, 1997, 37-46. This work is supported by NSF grant CCR 9528228. - 22.
- Shahrokhi, F., Sýkora, O., Székely, L. A., Vrto, I.,
On bipartite crossings, biplanar subgraphs, and the linear arrangement problem,
in Proc.
*5th Workshop Algorithms and Data Structures, (WADS'97), LNCS*1272, Springer-Verlag, 1997, 55-68. This work is supported by NSF grant CCR 9528228. - 23.
- Shahrokhi, F., Sýkora, O., Székely, L.A., and Vrto, I.,
Crossing Number Problems: Bounds and Applications, invited paper,
in
*Intuitive Geometry*eds. I. Bárány and K. Böröczky, Bolyai Society Mathematical Studies 6, 1997, 179-206. This work is supported by NSF grant CCR 9528228. - 24.
- Shahrokhi, F., Shi, W.,
Efficient Algorithms for Embedding Graphs on Books,
*Proceedings of COCOON 96, LNCS*Springer-Verlag, 1996, 162-168. - 25.
- Shahrokhi, F., Sýkora, O., Székely, L.A., and Vrto, I.,
Crossing Number of Meshes,
in
*Proceedings of Graph drawing 95 (GD95), LNCS 1027*, Springer-Verlag, 1996, 197-209. - 26.
- Shahrokhi, F. and Székely, L.A.,
On Group Invariant Flows and Applications,
*Graph Theory, Combinatorics, and Applications Proceedings of the 7th International Conference on Theory and Applications of Graphs*,*Wiley and Sons*, 1995, 1033-1042. - 27.
- Shahrokhi, F., Sýkora, O., Székely, L.A., and Vrto, I.,
Book embedding and Crossing Numbers,
in
*Proceedings of 20th International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS 903*, Springer-Verlag, 1995, 112-122. - 28.
- Shahrokhi, F., Székely L.A., and Vrto, I.,
Crossing Numbers of Graphs, Lower Bound Techniques and Algorithms: A Survey,
*Proc. of Graph Drawing 94 (GD94), LNCS*, 894, Spring Verlag, 1995, 131-142. - 29.
- Shahrokhi, F., Sýkora, O., Székely, L.A., and Vrto, I.,
Improved Bounds for Crossing Number of a Graph on a Compact 2-Manifold,
*Proceedings of 19th International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS*, 790, Springer-Verlag, 1993, 388-395. - 30.
- Shahrokhi, F. and Székely, L.A.,
Packet Routing in Graphs,
*Proceedings of 19th International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS*790, Springer-Verlag, 1993, 327-337. - 31.
- Pach, J., Shahrokhi, F. and Szegedy, M.,
Applications of Crossing Number,
*Proceedings of Tenth Annual ACM Symposium on Computational Geometry*, May 1994. - 32.
- Shahrokhi, F. and Székely, L.A.
*A New Approach to the Uniform Multicommodity Flow Problem*, 14th International Symposium on Mathematical Programming, Amsterdam, Aug. 1991. ( acceptance rate was 20%.) - 33.
- Shahrokhi, F. and Székely, L.A.,
Effective Lower Bounds for the Crossing Number, Bisection Width and
Balanced Vertex Separators in Terms of Symmetry,
*Proceedings of the Second Conference in Integer Programming and Combinatorial Optimization*, 1992, CMU Press, Pittsburgh, 102-114. - 34.
- Shahrokhi, F.,
Duality Theorems for the Maximum Concurrent Flow Problem,
*Proceedings of the Sixth International Conference on Theory and Applications of Graphs*, Wiley and Sons, 1991, 1075-1082. - 35.
- Shahrokhi, F. and Matula, D. W.,
On Solving Large Maximum Concurrent Flow Problems,
*Proceedings of ACM 1987 National Conference*, 205-209.

**Unpublished Technical Reports**

- 1.
- Shahrokhi, F., Shi, W. Polynomial time deterministic algorithms
for pagenumber, crossing and disjoint sets. DIMACS Tech. Report
TR:98-46, 1998.
- 2.
- Shahrokhi, F., Székely, L.A, Uniform Concurrent Multicommodity
Flow in Product Graphs,
Report 92744,
Institut Für Ökonometrie Und Operations Research
Rheinische Friedrich-Wilhelms-Universität, Bonn, 1992.
- 3.
- Shahrokhi, F., Székely, L.A, An Algebraic Approach to the Uniform
Multicommodity Flow Problem: Theory and Applications,
Report 92745,
Institut Für Ökonometrie Und Operations Research
Rheinische Friedrich-Wilhelms-Universität, Bonn, 1992.

**Funding**

**The National Science Foundations**

Solving crossing number problems with applications,
Principal Investigator,
CCR-9988525, $169,280, 2000-2003.

**The National Science Foundations**

Crossing number problems in geometric drawings of graphs,
Principal Investigator,
CCR-9528228, $48,800, 1996-1999.

**College of Art **** Sciences at UNT**

AMS Sectional Meeting in Columbia, South Carolina, March 2001,
$4,000.

**DIMACS**

$6000, 1998-1999.

**MCI Dallas**

$15,000, 1995.

**Various Small Internal Grants at UNT**

$8,000, 1989-2000.

**Abstracts and Presentations**

*The listed presentations do not include the talks given
for presenting the conference papers.*

Shahrokhi, F.,
*On Crossing Number Problems*,
Department of Mathematics, University of South Carolina, 1998.

Shahrokhi, F., *Crossing numbers: Bounds and Applications*,
1997 Workshop on Algorithmic Research in Midsouthwest (WARM'97),
UNT, 1997.

Shahrokhi, F., Sýkora, O., Székely L.A., and Vrto, I.,
*On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem*
AMS Meeting at Oaxaca, Mexico, December 1997 (Abstract).

Shahrokhi, F., Székely, L.A.,
*Uniform Concurrent Flow in Product Graphs* (Abstract),
27th Southeast International Conference in Combinatorics,
Graph Theory, and Computing, LSU 1996.

Shahrokhi, F., Sýkora, O., Székely L.A., and Vrto, I.,
*Bounds for the Crossing Number of a Graph on a Compact Two Manifold*,
presented in AMS National Meeting, May 1993, (Abstract) p. 410.

Shahrokhi, F.,
*Crossing Number of Symmetric Graphs on a Compact Two Manifold*,
presented in 1992 Workshop on Algorithmic Research in Midsouthwest (WARM'92),
SMU.

Shahrokhi, F. and Székely, L.A.,
*New Lower Bounds for the Crossing Number*, presented in Seventh
International Conference on Theory and Applications of Graphs, WMU, 1992.

Shahrokhi, F.,
*An Algebraic Approach to Concurrent Flows*,
presented at the Department of Computer Science, Texas A&M University,
1991.

Shahrokhi, F.,
*Lower Bounds for the Crossing Number*,
presented at at the Department of Computer Science,
Southern Methodist University 1991.

Shahrokhi, F.,
*On Concurrent Flows*,
presented at Department Computer Science,
Southern Methodist University, 1991.

Shahrokhi, F.,
*Solving Large Multicommodity Flows*, presented at BNR, 1990.

Shahrokhi, F. and Székely, L.A.,
*A Combinatorial Approach to Integral Multicommodity Flow Problems*,
presented in AMS National Meeting, March 1990.
(Invited Talk; Co-author presented the talk.)

Shahrokhi, F. and Barefoot, C.,
*1-Hamiltonian Connectivity of 4-Connected Halin Graphs*,
presented in International Southeast Conference on
Combinatorics and Computing, Boca Raton, 1989.

Shahrokhi, F.,
*On Solving the Universal Packet Routing Problems
for Parallel and Distributed Systems*
presented in 1989 New Mexico Computer Science Conference, Socorro, 1989.

Shahrokhi, F.,
*Communications Complexity and Routing in Parallel Computing*,
presented in 1988 New Mexico Computer Science Conference, Albuquerque, 1988.

Shahrokhi, F.,
*The Maximum Concurrent Flow Problem*,
presented at the Department of Mathematics,
Massachusetts Institute of Technology,
1987.

Matula, D.W., Shahrokhi, F., and Thompson, B.,
*Another Look at Divisive Hierarchical Clustering
Procedures*,
presented in 20th Annual International Conference
on Numerical Taxonomy (NT-20), 1986.

Shahrokhi, F.,
*An Efficient Routing Algorithm to Solve the
Maximum Concurrent Flow Problem with Applications to
the Packet Switched Telecommunication Networks and Cluster Analysis*,
presented in ACM 1986 National Conference.

Shahrokhi, F. and Matula, D.W.,
*An Efficient Iterative Solution to the Maximum Concurrent Flow Problem*,
presented in ORSA/TIMS 1985 Joint National Meeting, (Abstract) p. 136.

Matula, D.W., Helgason, R.V., Shahrokhi, F., Thompson, B.W.,
*Applications in Cluster Analysis of Maximum Concurrent Network Flows*,
presented in ORSA/TIMS 1985 Joint National Meeting, (Abstract) p. 136.

**Awards**

Service Recognition Award, UNT, 1999

Nominee (jointly with D. W. Matula) for D. Ray Fulkerson Prize
in discrete mathematics 1994.

Nominee for Decker Scholar award for excellence in research, UNT, 1993.

Nominee for Shelton teaching award for excellence in teaching, UNT, 1993.

Nominee for Shelton teaching award for excellence in teaching, UNT, 1994.

Nominee for Honors Professor's ward award for excellence in teaching UNT,
1994.

**Additional Professional Activities**

**Co-organizer** Special Session in Discrete and Computational Geometry,
and Graph Drawing,
AMS meeting at Columbia, South Carolina, March 2001,
24 speakers, Four Sessions.

**Program Director**
1997 Workshop on Algorithmic Research in Midsouthwest (WARM'97),
University of North Texas, March 8, 1997.
This workshop is sponsored by a consortium of computer science departments
in the area, including U. Texas, U. Oklahoma, Southern Methodist U.,
Texas A.& M., Rice U., Louisiana State U., U. Southwestern Louisiana,
U. of North Texas and, U. Texas - Dallas.

**Reviewer**
SODA2000, STOC2000, SODA94, Algorithmica, Disc. and Comp.
Geom., Journal of Operations Research,
Journal of Graph Theory, SIAM Journal on
Computing, Journal of Algorithms, ORSA Journal on Computing, INFOR, Pattern
Recognition, Networks, Seventh International Conference on Theory and
Application of Graphs, IEEE Trans. on Computers.

**Session Chair**: Fifth and Sixth, IEEE Symposium On Parallel and
Distributed Processing, Dallas, TX, 1993, 1994.

**Invited Participant**

*Center for Discrete Mathematics and Theoretical Computer Science*
(DIMACS), Workshop for Graph Drawing 94, Princeton University, 1994

*Center for Discrete Mathematics and Theoretical Computer
Science* (DIMACS), Rutgers University,
Workshop for Approximation Algorithms,
1993.

NSF Workshop on *Probabilistic Methods in Combinatorial Optimization*,
Dept. of Mathematics, Johns Hopkins University,
1988.

NSF-CBMS Workshop on *Algorithms and Complexity*, Colorado College,
1987.

**Invited Speaker**

Sixth and Seventh International Conference on Theory and
Applications of Graphs, Kalamazoo, 1988 and 1992.

Fifth and Sixth International Conference on Random Graphs
and Probabilistic Methods, Poznan, Poland, 1991, 1993. ( I was invited but could not go)

**TEACHING**

**Undergraduate Classes Taught**

Data Structures, Discrete Mathematics, Design and Analysis of Algorithm,
Introduction to Programming, Networks, Circuit Design, Digital Logic Design.

**Graduate Classes Taught**

Algorithm Design, Approximation algorithms,
Combinatorial Optimization, Complexity Theory,
Graph Theory, Advanced Algorithms, Automata Theory and Compiler Design.

**Undergraduate Student Supervision**

**Directed Studies** Powel 1994, Eaton 1994, Edwards 1995.

**Graduate Student Supervision**

**MS Students**, Eric Lee 1989, Shi 1990, Lei 1990, Behzadnoori 1991,
Kaizer 1991, Chapin 1993, Kolgeshev 1994, Azzizgolu, 1995,
Dietz 1995, Kumar 1995, Lee 1995, Sethi 1996, Hughes, 1997, Yildiz 1997.

**Ph.D. Students** Jamily and Lin 1994; (These students did not finish.)

Member of about 8 Ph.D. committees, since 1989.

**Teaching Scores at UNT**

Course | Semester | My score | Department average |

csci6330 | fall94 | 4.57 | 3.40 |

csci3400 | fall94 | 4.63 | 3.40 |

csci5370 | spring95 | 4.1 | 3.64 |

csci3400 | spring95 | 4.55 | 3.64 |

csci6330 | fall95 | 4.25 | 3.64 |

csci5450 | fall95 | 4.08 | 3.64 |

csci3400 | spring96 | 4.21 | 3.95 |

csci3400 | spring96 | 4.25 | 3.95 |

csci6330 | fall96 | 4.0 | 3.95 |

csci3400 | fall96 | 4.42 | 3.95 |

csc5370 | spring97 | 4.5 | 3.70 |

csci3400 | spring97 | 4.0 | 3.70 |

csci6330 | fall98 | 4.0 | 3.73 |

csci4450 | fall98 | 3.0 | 3.73 |

csci5450 | spring99 | 3.89 | 3.89 |

csci3400 | spring99 | 3.08 | 3.89 |

csci5450 | summer99 | 4.60 | |

csci5370 | summer99 | 4.83 | |

csci6330 | fall00 | 4.6 | 3.89 |

csci3400 | fall00 | 4.27 | 3.89 |

**SERVICE AT UNT **

**Service to the Department of Computer Science**

1999-2000 | Chair, Faculty Recruitment Committee |

1998-2000 |
PAC
and executive committee |

1996-1997 |
PAC and Executive committee |

1996 |
Re-wrote and revised the promotion and tenure guidelines and procedures |

1996-1997 |
Coordinator for Research Seminars |

1996-1997 |
PAC and Graduate Committee |

1996-1997 |
Faculty Recruitment Committee |

1996 (Spring) |
Add-Hoc appeal Committee of Dr. Brazile |

1995-1996 |
Chair, Faculty Recruitment Committee |

1996 |
Chair, Search Committee for Hiring a Chairman |

in the Dept. of Comp. Sci | |

1995-1996 |
Chair, PAC and a member of the Undergraduate and Graduate Committees |

1994-1995 |
PAC and Graduate Committee |

1994-1995 |
Ad-hoc Committee for writing the Charter in the Dept. of Comp. Sci. |

1993-1994 |
Graduate Committee |

1992-1993 |
Undergraduate Committee |

1990-1992 |
Graduate Committee |

1990-1992 |
Coordinator for Research Seminars |

1989-1992 |
Graduate Committee |

**Service to the College and the University **

1996 |
Add-Hoc Appeal Committee (tenure) of Dr. Joe Prez, in the College of Art and Sciences |

1994-1995 |
Faculty Judge for Traffic Appeal Court at the University of North Texas |

1991-1993 |
Faculty Judge for Traffic Appeal Court at the University of North Texas |