next up previous
Next: About this document ...

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 $C_n\times C_m$ 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



 
next up previous
Next: About this document ...
Farhad Shahrohki
2000-09-26